Bioinformatics of large-scale protein interaction networks

We survey recent techniques for construction and prediction of large-scale protein interaction networks, focusing on computational processing steps. Special emphasis is placed on critical assessment of data completeness and reliability of the various approaches. Once built, protein interaction networks can be used for functional annotation or to generate higher-level biological hypotheses on pathways.     

Comparative analysis of protein interaction networks

Recent advances in proteomics and computational biology have lead to a flood of protein interaction data and resulting interaction networks (e.g. (Gavin et al., 2002)). Here I first analyse the status and quality of parts lists (genes and proteins), then comparatively assess large-scale protein interaction data (von Mering et al., 2002) and finally try to identify biological meaningful units (e.g. pathways, cellular processes) within interaction networks that are derived from the conservation of gene neighborhood (Snel et al., 2002). Possible extensions of gene neighborhood analysis to eukaryotes (von Mering and Bork, 2002) will be discussed.     

Computational analysis of human protein interaction networks

Large amounts of human protein interaction data have been produced by experiments and prediction methods. However, the experimental coverage of the human interactome is still low in contrast to predicted data. To gain insight into the value of publicly available human protein network data, we compared predicted datasets, high-throughput results from yeast two-hybrid screens, and literature-curated protein-protein interactions. This evaluation is not only important for further methodological improvements, but also for increasing the confidence in functional hypotheses derived from predictions. Therefore, we assessed the quality and the potential bias of the different datasets using functional similarity based on the Gene Ontology, structural iPfam domain-domain interactions, likelihood ratios, and topological network parameters. This analysis revealed major differences between predicted datasets, but some of them also scored at least as high as the experimental ones regarding multiple quality measures. Therefore, since only small pair wise overlap between most datasets is observed, they may be combined to enlarge the available human interactome data. For this purpose, we additionally studied the influence of protein length on data quality and the number of disease proteins covered by each dataset. We could further demonstrate that protein interactions predicted by more than one method achieve an elevated reliability.     

Phylogenetic analysis of modularity in protein interaction networks

Background  

In systems biology, comparative analyses of molecular interactions across diverse species indicate that conservation and divergence of networks can be used to understand functional evolution from a systems perspective. A key characteristic of these networks is their modularity, which contributes significantly to their robustness, as well as adaptability. Consequently, analysis of modular network structures from a phylogenetic perspective may be useful in understanding the emergence, conservation, and diversification of functional modularity.     

Interactive three-dimensional visualization and contextual analysis of protein interaction networks

To understand the biology of the interactome, the covisualization of protein interactions and other protein-related data is required. In this study, we have adapted a 3-D network visualization platform, GEOMI, to allow the coanalysis of protein-protein interaction networks with proteomic parameters such as protein localization, abundance, physicochemical parameters, post-translational modifications, and gene ontology classification. Working with Saccharomyces cerevisiae data, we show that rich and interactive visualizations, constructed from multidimensional orthogonal data, provide insights on the complexity of the interactome and its role in biological processes and the architecture of the cell. We present the first organelle-specific interaction networks, that provide subinteractomes of high biological interest. We further present some of the first views of the interactome built from a new combination of yeast two-hybrid data and stable protein complexes, which are likely to approximate the true workings of stable and transient aspects of the interactome. The GEOMI tool and all interactome data are freely available by contacting the authors.     

Gene essentiality and the topology of protein interaction networks

The mechanistic bases for gene essentiality and for cell mutational resistance have long been disputed. The recent availability of large protein interaction databases has fuelled the analysis of protein interaction networks and several authors have proposed that gene dispensability could be strongly related to some topological parameters of these networks. However, many results were based on protein interaction data whose biases were not taken into account. In this article, we show that the essentiality of a gene in yeast is poorly related to the number of interactants (or degree) of the corresponding protein and that the physiological consequences of gene deletions are unrelated to several other properties of proteins in the interaction networks, such as the average degrees of their nearest neighbours, their clustering coefficients or their relative distances. We also found that yeast protein interaction networks lack degree correlation, i.e. a propensity for their vertices to associate according to their degrees. Gene essentiality and more generally cell resistance against mutations thus seem largely unrelated to many parameters of protein network topology.     

Modular organization of protein interaction networks

MOTIVATION: Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules. Identifying these modules is essential to understand the organization of biological systems. RESULT: In this paper, we present a framework to identify modules within biological networks. In this approach, the concept of degree is extended from the single vertex to the sub-graph, and a formal definition of module in a network is used. A new agglomerative algorithm was developed to identify modules from the network by combining the new module definition with the relative edge order generated by the Girvan-Newman (G-N) algorithm. A JAVA program, MoNet, was developed to implement the algorithm. Applying MoNet to the yeast core protein interaction network from the database of interacting proteins (DIP) identified 86 simple modules with sizes larger than three proteins. The modules obtained are significantly enriched in proteins with related biological process Gene Ontology terms. A comparison between the MoNet modules and modules defined by Radicchi et al. (2004) indicates that MoNet modules show stronger co-clustering of related genes and are more robust to ties in betweenness values. Further, the MoNet output retains the adjacent relationships between modules and allows the construction of an interaction web of modules providing insight regarding the relationships between different functional modules. Thus, MoNet provides an objective approach to understand the organization and interactions of biological processes in cellular systems. AVAILABILITY: MoNet is available upon request from the authors.     

Modular organization of protein interaction networks

Bioinformatics (2007) 23(2),     

Antagonism and bistability in protein interaction networks

A protein interaction network (PIN) is a set of proteins that modulate one another's activities by regulated synthesis and degradation, by reversible binding to form complexes, and by catalytic reactions (e.g., phosphorylation and dephosphorylation). Most PINs are so complex that their dynamical characteristics cannot be deduced accurately by intuitive reasoning alone. To predict the properties of such networks, many research groups have turned to mathematical models (differential equations based on standard biochemical rate laws, e.g., mass-action, Michaelis-Menten, Hill). When using Michaelis-Menten rate expressions to model PINs, care must be exercised to avoid making inconsistent assumptions about enzyme-substrate complexes. We show that an appealingly simple model of a PIN that functions as a bistable switch is compromised by neglecting enzyme-substrate intermediates. When the neglected intermediates are put back into the model, bistability of the switch is lost. The theory of chemical reaction networks predicts that bistability can be recovered by adding specific reaction channels to the molecular mechanism. We explore two very different routes to recover bistability. In both cases, we show how to convert the original 'phenomenological' model into a consistent set of mass-action rate laws that retains the desired bistability properties. Once an equivalent model is formulated in terms of elementary chemical reactions, it can be simulated accurately either by deterministic differential equations or by Gillespie's stochastic simulation algorithm.     

蛋白质网络聚类算法分析平台的设计与实现

蛋白质网络聚类是识别功能模块的重要手段,不仅有利于理解生物系统的组织结构,对预测蛋白质功能也具有重要的意义。针对目前蛋白质网络聚类算法缺乏有效分析软件的事实,本文设计并实现了一个新的蛋白质网络聚类算法分析平台ClusterE。该平台实现了查全率、查准率、敏感性、特异性、功能富集分析等聚类评估方法,并且集成了FAG-EC、Dpclus、Monet、IPC-MCE、IPCA等聚类算法,不仅可以对蛋白质网络聚类分析结果进行可视化,并且可以在不同聚类分析指标下对多个聚类算法进行可视化比较与分析。该平台具有良好的扩展性,其中聚类算法以及聚类评估方法都是以插件形式集成到系统中。     

Bioinformatics visualization and integration with open standards: the Bluejay genomic browser

We have created a new Java-based integrated computational environment for the exploration of genomic data, called Bluejay. The system is capable of using almost any XML file related to genomic data. Non-XML data sources can be accessed via a proxy server. Bluejay has several features, which are new to Bioinformatics, including an unlimited semantic zoom capability, coupled with Scalable Vector Graphics (SVG) outputs; an implementation of the XLink standard, which features access to MAGPIE Genecards as well as any BioMOBY service accessible over the Internet; and the integration of gene chip analysis tools with the functional assignments. The system can be used as a signed web applet, Web Start, and a local stand-alone application, with or without connection to the Internet. It is available free of charge and as open source via http://bluejay.ucalgary.ca.     

Identification of protein complexes from multi-relationship protein interaction networks

Background

Protein complexes play an important role in biological processes. Recent developments in experiments have resulted in the publication of many high-quality, large-scale protein-protein interaction (PPI) datasets, which provide abundant data for computational approaches to the prediction of protein complexes. However, the precision of protein complex prediction still needs to be improved due to the incompletion and noise in PPI networks.

Results

There exist complex and diverse relationships among proteins after integrating multiple sources of biological information. Considering that the influences of different types of interactions are not the same weight for protein complex prediction, we construct a multi-relationship protein interaction network (MPIN) by integrating PPI network topology with gene ontology annotation information. Then, we design a novel algorithm named MINE (identifying protein complexes based on Multi-relationship protein Interaction NEtwork) to predict protein complexes with high cohesion and low coupling from MPIN.

Conclusions

The experiments on yeast data show that MINE outperforms the current methods in terms of both accuracy and statistical significance.

     

IDDI: integrated domain-domain interaction and protein interaction analysis system

Background

Deciphering protein-protein interaction (PPI) in domain level enriches valuable information about binding mechanism and functional role of interacting proteins. The 3D structures of complex proteins are reliable source of domain-domain interaction (DDI) but the number of proven structures is very limited. Several resources for the computationally predicted DDI have been generated but they are scattered in various places and their prediction show erratic performances. A well-organized PPI and DDI analysis system integrating these data with fair scoring system is necessary.

Method

We integrated three structure-based DDI datasets and twenty computationally predicted DDI datasets and constructed an interaction analysis system, named IDDI, which enables to browse protein and domain interactions with their relationships. To integrate heterogeneous DDI information, a novel scoring scheme is introduced to determine the reliability of DDI by considering the prediction scores of each DDI and the confidence levels of each prediction method in the datasets, and independencies between predicted datasets. In addition, we connected this DDI information to the comprehensive PPI information and developed a unified interface for the interaction analysis exploring interaction networks at both protein and domain level.

Result

IDDI provides 204,705 DDIs among total 7,351 Pfam domains in the current version. The result presents that total number of DDIs is increased eight times more than that of previous studies. Due to the increment of data, 50.4% of PPIs could be correlated with DDIs which is more than twice of previous resources. Newly designed scoring scheme outperformed the previous system in its accuracy too. User interface of IDDI system provides interactive investigation of proteins and domains in interactions with interconnected way. A specific example is presented to show the efficiency of the systems to acquire the comprehensive information of target protein with PPI and DDI relationships. IDDI is freely available at http://pcode.kaist.ac.kr/iddi/.

     

Pairwise alignment of protein interaction networks.

With an ever-increasing amount of available data on protein-protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein-protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost.     

Statistics for proteomics: experimental design and 2-DE differential analysis

Proteomics relies on the separation of complex protein mixtures using bidimensional electrophoresis. This approach is largely used to detect the expression variations of proteins prepared from two or more samples. Recently, attention was drawn on the reliability of the results published in literature. Among the critical points identified were experimental design, differential analysis and the problem of missing data, all problems where statistics can be of help. Using examples and terms understandable by biologists, we describe how a collaboration between biologists and statisticians can improve reliability of results and confidence in conclusions.     

Improving evolutionary models of protein interaction networks

MOTIVATION: Theoretical models of biological networks are valuable tools in evolutionary inference. Theoretical models based on gene duplication and divergence provide biologically plausible evolutionary mechanics. Similarities found between empirical networks and their theoretically generated counterpart are considered evidence of the role modeled mechanics play in biological evolution. However, the method by which these models are parameterized can lead to questions about the validity of the inferences. Selecting parameter values in order to produce a particular topological value obfuscates the possibility that the model may produce a similar topology for a large range of parameter values. Alternately, a model may produce a large range of topologies, allowing (incorrect) parameter values to produce a valid topology from an otherwise flawed model. In order to lend biological credence to the modeled evolutionary mechanics, parameter values should be derived from the empirical data. Furthermore, recent work indicates that the timing and fate of gene duplications are critical to proper derivation of these parameters. RESULTS: We present a methodology for deriving evolutionary rates from empirical data that is used to parameterize duplication and divergence models of protein interaction network evolution. Our method avoids shortcomings of previous methods, which failed to consider the effect of subsequent duplications. From our parameter values, we find that concurrent and existing existing duplication and divergence models are insufficient for modeling protein interaction network evolution. We introduce a model enhancement based on heritable interaction sites on the surface of a protein and find that it more closely reflects the high clustering found in the empirical network.