Search

The core–periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core–periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

Proteins are known to interact with each other by forming protein complexes and in order to perform specific biological functions. Many community detection methods have been devised for the discovery of protein complexes in protein interaction networks. One common problem in current agglomerative community detection approaches is that vertices with just one neighbor are often classified as separate clusters, which does not make sense for complex identification. Also, a major limitation of agglomerative techniques is that their computational efficiency do not scale well to large protein interaction networks (PINs). In this paper, we propose a new agglomerative algorithm, FAC-PIN, based on a local premetric of relative vertex-to-vertex clustering value and which addresses the above two issues. Our proposed FAC-PIN method is applied to eight PINs from different species, and the identified complexes are validated using experimentally verified complexes. The preliminary computational results show that FAC-PIN can discover protein complexes from PINs more accurately and faster than the HC-PIN and CNM algorithms, the current state-of-the-art agglomerative approaches to complex prediction.

Understanding gene interactions is a fundamental question in uncovering the underlying biological relations that enable successful functioning of living organisms. The modeling of gene regulations is usually done using DNA microarray data. However, presence of noise and the scarcity of microarray data affect the reconstruction of gene regulatory networks. In this paper, we propose a novel co-learning based fusion algorithm using the dynamic Bayesian netowrk (DBN) formalism for reconstruction of gene regulatory networks which incorporates knowledge obtained from protein-protein interaction networks to improve network accuracy. The proposed approach is efficient and naturally amenable to parallel computation. We apply the algorithm on the well-known Saccharomyces cerevisiae gene expression data that shows the effectiveness of our approach.

Protein interaction networks are of great importance to understand the biological cellular process. Recent advances in high-throughput detection methods, such as the yeast two hybrid method, have given researchers access to large volumes of PPI network data. However, protein interaction databases published by different research groups use different protein naming systems and have different levels of reliability. In this paper we design ProteinNET, a protein interaction network integration system, to integrate protein interaction databases from different sources and improve the quality of the protein interaction network by using noise reduction techniques. In addition, the proteinNET system provides five methods to visualize the protein interaction network. The ProteinNET system can help researchers explore the protein interaction network of different data sources.

In this chapter, we present efficient and accurate methods to analyze biological networks. Biological networks show how different biochemical entities interact with each other to perform vital functions for the survival of an organism. Three main types of biological networks are protein interaction networks, metabolic pathways and regulatory networks. In this work, we focus on alignment of metabolic networks.

Predicting protein function is one of the most challenging problems of the post-genomic era. The development of experimental methods for genome scale analysis of molecular interaction networks has provided new approaches to inferring protein function. In this paper we introduce a new graph-based semi-supervised classification algorithm Sequential Linear Neighborhood Propagation (SLNP), which addresses the problem of the classification of partially labeled protein interaction networks. The proposed SLNP firstly constructs a sequence of node sets according to their shortest distance to the labeled nodes, and then predicts the function of the unlabel proteins from the set closer to labeled one, using Linear Neighborhood Propagation. Its performance is assessed on the Saccharomyces cerevisiae PPI network data sets with good results compared with three current state-of-the-art algorithms.

This paper introduces an algorithm for network community detection called DEEN, (Delete Edges and Expand Nodes) consisting of two simple steps. First edges of the graph estimated to connect different clusters are detected and removed, next the resulting graph is used for generating communities by expanding seed nodes.

Most of a cell’s functional processes involve interactions among proteins, and a key challenge in proteomics is to better understand these complex interaction graphs at a systems level. Because of their importance in development and disease, protein-protein interactions (PPIs) have been the subject of intense research in recent years. In addition, a greater understanding of PPIs can be achieved through the detailed investigation of the protein domain interactions which mediate PPIs. In this chapter, we describe recent efforts to predict interactions between proteins and between protein domains. We also describe methods that attempt to use protein interaction data to infer protein function. Protein-protein interactions directly contribute to protein functions, and implications about functions can often be made via PPI studies. These inferences are based on the premise that the function of a protein may be discovered by studying its interaction with one or more proteins of known functions. The second part of this chapter reviews recent computational approaches to predict protein functions from PPI networks.

Identifying essential proteins is important for understanding the minimal requirements for cellular survival and development. Fast growth in the amount of available protein-protein interactions has produced unprecedented opportunities for detecting protein essentiality on network level. A series of centrality measures have been proposed to discover essential proteins based on network topology. However, most of them treat all interactions equally and are sensitive to false positives. In this paper, six standard centrality measures are redefined to be used in weighted network. A new method for weighing protein-protein interactions is proposed based on the combination of logistic regression-based model and function similarity. The experimental results on yeast network show that the weighting method can improve the performance of centrality measures considerably. More essential proteins are discovered by the weighted centrality measures than by the original centrality measures used in unweighted network. Even about 20% improvements are obtained from closeness centrality and subgraph centrality.

Real PPI networks commonly have large size. Functional modules in them are usually overlapping and hierarchical. So it is significant to identify both overlapping and hierarchical modules with low time complexity. However previous methods can not do it. A new agglomerative algorithm, MOMA, is proposed in the paper to resolve this problem. MOMA classifies subgraphs into clusters and vertices. Clusters can overlap each other. MOMA identifies overlapping and hierarchical functional modules by merging overlapping subgraphs. Its time complexity is O(N2). We apply MOMA, G-N algorithm and Cfinder on the yeast core PPI network. Comparing with G-N algorithm, MOMA can identify overlapping modules. Comparing with Cfinder, MOMA can identify hierarchical modules. Distributions of the lowest P-value show that the module set identified by MOMA has the stronger biological significance than those identified by the other two algorithms.

High-throughput experimental technologies, along with computational predictions, have resulted in large-scale biological networks for numerous organisms. Global analyses of biological networks provide new opportunities for revealing protein functions and pathways, and for uncovering cellular organization principles. In my talk, I will discuss a number of approaches we have developed over the years for the complementary problems of predicting interactions and analyzing interaction networks. First, I will describe a genomic approach for uncovering high-confidence regulatory interactions, and show how it can be effectively combined with a framework for predicting regulatory interactions for proteins with known structural domains but unknown binding specificity. Next, I will describe algorithms for analyzing protein interaction networks in order to uncover protein function and functional modules, and demonstrate the importance of considering the topological structure of interaction networks in order to make high quality predictions. Finally, I will present a framework for explicitly incorporating known attributes of individual proteins into the analysis of biological networks, and utilize it to discover recurring network patterns underlying a range of biological processes.

As advances in the technologies of predicting protein interactions, huge data sets portrayed as networks have been available. Several graph clustering approaches have been proposed to detect functional modules from such networks. However, all methods of predicting protein interactions are known to yield a nonnegligible amount of false positives. Most of the graph clustering algorithms are challenging to be used in the network with high false positives. We extend the protein interaction network from unweighted graph to weighted graph and propose an algorithm for hierarchically clustering in the weighted graph. The proposed algorithm HC-Wpin is applied to the protein interaction network of S.cerevisiae and the identified modules are validated by GO annotations. Many significant functional modules are detected, most of which are corresponding to the known complexes. Moreover, our algorithm HC-Wpin is faster and more accurate compared to other previous algorithms. The program is available at http://bioinfo.csu.edu.cn/limin/HC-Wpin.

Association analysis is one of the most popular analysis paradigms in data mining. Despite the solid foundation of association analysis and its potential applications, this group of techniques is not as widely used as classification and clustering, especially in the domain of bioinformatics and computational biology. In this paper, we present different types of association patterns and discuss some of their applications in bioinformatics. We present a case study showing the usefulness of association analysis-based techniques for pre-processing protein interaction networks for the task of protein function prediction. Finally, we discuss some of the challenges that need to be addressed to make association analysis-based techniques more applicable for a number of interesting problems in bioinformatics.

Identification of functional modules in large protein interactionnetworks is crucial to understand principles of cellular organization,processes and functions. As a protein can perform different functions,functional modules overlap with each other. In this paper, we presenteda new algorithm OMFinder for mining overlapping functional modulesin protein interaction networks by using graph split and reduction. Weapplied algorithm OMFinder to the core protein interaction network ofbudding yeast collected from DIP database. The experimental resultsshowed that algorithm OMFinder detected many significant overlappingfunctional modules with various topologies. The significances of identifiedmodules were evaluated by using functional categories from MIPSdatabase. Most importantly, our algorithm had very low discard ratecompared to other approaches of detecting overlapping modules.

Protein complexes, identified as functional modules in protein interaction networks, are cellular entities that perform certain biological functions. Revealing these modular structures is significant in understanding how cells function. Protein interaction networks can be constructed by representing nodes as proteins and edges as interactions between proteins. In this paper, we use a graph based distance measure, n-clubs, to detect protein complexes in these interaction networks. The quality of clustering protein interaction networks using n-clubs is comparable to that obtained by best known clustering algorithms applied to various protein networks. Moreover, n-clubs approach is driven by a single parameter n in contrast to other clustering algorithms which have numerous parameters to tune for best results.

In this paper, we propose a pattern-based protein function annotation framework, employing protein interaction networks, to predict annotation functions of proteins. More specifically, we first detect patterns that appear in the neighborhood of proteins with a particular functionality, and then transfer annotations between two proteins only if they have similar annotation patterns. We show that, in comparison with other techniques, our approach predicts protein annotations more effectively. Our technique (a) produces the highest prediction accuracy of 70-80% precision and recall for different organism specific datasets, and (b) is robust to false positives in protein interaction networks.

The increasing growth of data on protein-protein interaction (PPI) networks has boosted research on their comparative analysis. In particular, recent studies proposed models and algorithms for performing network alignment, the comparison of networks across species for discovering conserved modules. Common approaches for this task construct a merged representation of the considered networks, called alignment graph, and search the alignment graph for conserved networks of interest using greedy techniques. In this paper we propose a modular approach to this task. First, each network to be compared is divided into small subnets which are likely to contain conserved modules. To this aim, we develop an algorithm for dividing PPI networks that combines a graph theoretical property(articulation) with a biological one (orthology). Next, network alignment is performed on pairs of resulting subnets from different species. We tackle this task by means of a state-of-the-art alignment graph model for constructing alignment graphs, and an exact algorithm for searching in the alignment graph. Results of experiments show the ability of this approach to discover accurate conserved modules, and substantiate the importance of the notions of orthology and articulation for performing comparative network analysis in a modular fashion.

We describe a new approach for comparing cellular-biological networks, and finding conserved regions in two or more such networks. We use the length of describing one network, given the description of the other one, as a distance measure. We employ these distances as inputs for generating phylogenetic trees. Our algorithms are fast enough for generating phylogenetic tree of more than two hundreds metabolic networks that appear in KEGG. Using KEGG's metabolic networks as our starting point, we got trees that are not perfect, but are surprisingly good. We also found conserved regions among more than a dozen metabolic networks, and among two protein interaction networks. These conserved regions seem biologically relevant, proving the viability of our approach.

We have combined four different types of functional genomic data to create high coverage protein interaction networks for 11 microbes. Our integration algorithm naturally handles statistically dependent predictors and automatically corrects for differing noise levels and data corruption in different evidence sources. We find that many of the predictions in each integrated network hinge on moderate but consistent evidence from multiple sources rather than strong evidence from a single source, yielding novel biology which would be missed if a single data source such as coexpression or coinheritance was used in isolation. In addition to statistical analysis, we demonstrate via case study that these subtle interactions can discover new aspects of even well studied functional modules. Our work represents the largest collection of probabilistic protein interaction networks compiled to date, and our methods can be applied to any sequenced organism and any kind of experimental or computational technique which produces pairwise measures of protein interaction.

The interpretation of large-scale protein network data depends on our ability to identify significant sub-structures in the data, a computationally intensive task. Here we adapt and extend efficient techniques for finding paths in graphs to the problem of identifying pathways in protein interaction networks. We present linear-time algorithms for finding paths in networks under several biologically-motivated constraints. We apply our methodology to search for protein pathways in the yeast protein-protein interaction network. We demonstrate that our algorithm is capable of reconstructing known signaling pathways and identifying functionally enriched paths in an unsupervised manner. The algorithm is very efficient, computing optimal paths of length 8 within minutes and paths of length 10 in less than two hours.

This is a brief description of a new program for drawing protein interactions in three-dimensional space. Our program divides nodes into three groups: biconnected subgraph in the center, terminal nodes at the outermost region, and the rest in between them. Experimental results show that the program efficiently generates a clear and aesthetically pleasing drawing of large-scale protein interaction networks and that it is an order of magnitude faster than other force-directed layouts.