Identification of functional modules from conserved ancestral protein-protein interactions

MOTIVATION: The increasing availability of large-scale protein-protein interaction (PPI) data has fueled the efforts to elucidate the building blocks and organization of cellular machinery. Previous studies have shown cross-species comparison to be an effective approach in uncovering functional modules in protein networks. This has in turn driven the research for new network alignment methods with a more solid grounding in network evolution models and better scalability, to allow multiple network comparison. RESULTS: We develop a new framework for protein network alignment, based on reconstruction of an ancestral PPI network. The reconstruction algorithm is built upon a proposed model of protein network evolution, which takes into account phylogenetic history of the proteins and the evolution of their interactions. The application of our methodology to the PPI networks of yeast, worm and fly reveals that the most probable conserved ancestral interactions are often related to known protein complexes. By projecting the conserved ancestral interactions back onto the input networks we are able to identify the corresponding conserved protein modules in the considered species. In contrast to most of the previous methods, our algorithm is able to compare many networks simultaneously. The performed experiments demonstrate the ability of our method to uncover many functional modules with high specificity. AVAILABILITY: Information for obtaining software and supplementary results are available at http://bioputer.mimuw.edu.pl/papers/cappi.     

Network archaeology: uncovering ancient networks from present-day interactions

What proteins interacted in a long-extinct ancestor of yeast? How have different members of a protein complex assembled together over time? Our ability to answer such questions has been limited by the unavailability of ancestral protein-protein interaction (PPI) networks. To overcome this limitation, we propose several novel algorithms to reconstruct the growth history of a present-day network. Our likelihood-based method finds a probable previous state of the graph by applying an assumed growth model backwards in time. This approach retains node identities so that the history of individual nodes can be tracked. Using this methodology, we estimate protein ages in the yeast PPI network that are in good agreement with sequence-based estimates of age and with structural features of protein complexes. Further, by comparing the quality of the inferred histories for several different growth models (duplication-mutation with complementarity, forest fire, and preferential attachment), we provide additional evidence that a duplication-based model captures many features of PPI network growth better than models designed to mimic social network growth. From the reconstructed history, we model the arrival time of extant and ancestral interactions and predict that complexes have significantly re-wired over time and that new edges tend to form within existing complexes. We also hypothesize a distribution of per-protein duplication rates, track the change of the network''s clustering coefficient, and predict paralogous relationships between extant proteins that are likely to be complementary to the relationships inferred using sequence alone. Finally, we infer plausible parameters for the model, thereby predicting the relative probability of various evolutionary events. The success of these algorithms indicates that parts of the history of the yeast PPI are encoded in its present-day form.     

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.     

Generative probabilistic models for protein-protein interaction networks--the biclique perspective

MOTIVATION: Much of the large-scale molecular data from living cells can be represented in terms of networks. Such networks occupy a central position in cellular systems biology. In the protein-protein interaction (PPI) network, nodes represent proteins and edges represent connections between them, based on experimental evidence. As PPI networks are rich and complex, a mathematical model is sought to capture their properties and shed light on PPI evolution. The mathematical literature contains various generative models of random graphs. It is a major, still largely open question, which of these models (if any) can properly reproduce various biologically interesting networks. Here, we consider this problem where the graph at hand is the PPI network of Saccharomyces cerevisiae. We are trying to distinguishing between a model family which performs a process of copying neighbors, represented by the duplication-divergence (DD) model, and models which do not copy neighbors, with the Barabási-Albert (BA) preferential attachment model as a leading example. RESULTS: The observed property of the network is the distribution of maximal bicliques in the graph. This is a novel criterion to distinguish between models in this area. It is particularly appropriate for this purpose, since it reflects the graph's growth pattern under either model. This test clearly favors the DD model. In particular, for the BA model, the vast majority (92.9%) of the bicliques with both sides ≥4 must be already embedded in the model's seed graph, whereas the corresponding figure for the DD model is only 5.1%. Our results, based on the biclique perspective, conclusively show that a na?ve unmodified DD model can capture a key aspect of PPI networks.     

Modularity in the evolution of yeast protein interaction network

Protein interaction networks are known to exhibit remarkable structures: scale-free and small-world and modular structures. To explain the evolutionary processes of protein interaction networks possessing scale-free and small-world structures, preferential attachment and duplication-divergence models have been proposed as mathematical models. Protein interaction networks are also known to exhibit another remarkable structural characteristic, modular structure. How the protein interaction networks became to exhibit modularity in their evolution? Here, we propose a hypothesis of modularity in the evolution of yeast protein interaction network based on molecular evolutionary evidence. We assigned yeast proteins into six evolutionary ages by constructing a phylogenetic profile. We found that all the almost half of hub proteins are evolutionarily new. Examining the evolutionary processes of protein complexes, functional modules and topological modules, we also found that member proteins of these modules tend to appear in one or two evolutionary ages. Moreover, proteins in protein complexes and topological modules show significantly low evolutionary rates than those not in these modules. Our results suggest a hypothesis of modularity in the evolution of yeast protein interaction network as systems evolution.     

Reconstructing Genome-Wide Protein–Protein Interaction Networks Using Multiple Strategies with Homologous Mapping

Background

One of the crucial steps toward understanding the biological functions of a cellular system is to investigate protein–protein interaction (PPI) networks. As an increasing number of reliable PPIs become available, there is a growing need for discovering PPIs to reconstruct PPI networks of interesting organisms. Some interolog-based methods and homologous PPI families have been proposed for predicting PPIs from the known PPIs of source organisms.

Results

Here, we propose a multiple-strategy scoring method to identify reliable PPIs for reconstructing the mouse PPI network from two well-known organisms: human and fly. We firstly identified the PPI candidates of target organisms based on homologous PPIs, sharing significant sequence similarities (joint E-value ≤ 1 × 10⁻⁴⁰), from source organisms using generalized interolog mapping. These PPI candidates were evaluated by our multiple-strategy scoring method, combining sequence similarities, normalized ranks, and conservation scores across multiple organisms. According to 106,825 PPI candidates in yeast derived from human and fly, our scoring method can achieve high prediction accuracy and outperform generalized interolog mapping. Experiment results show that our multiple-strategy score can avoid the influence of the protein family size and length to significantly improve PPI prediction accuracy and reflect the biological functions. In addition, the top-ranked and conserved PPIs are often orthologous/essential interactions and share the functional similarity. Based on these reliable predicted PPIs, we reconstructed a comprehensive mouse PPI network, which is a scale-free network and can reflect the biological functions and high connectivity of 292 KEGG modules, including 216 pathways and 76 structural complexes.

Conclusions

Experimental results show that our scoring method can improve the predicting accuracy based on the normalized rank and evolutionary conservation from multiple organisms. Our predicted PPIs share similar biological processes and cellular components, and the reconstructed genome-wide PPI network can reflect network topology and modularity. We believe that our method is useful for inferring reliable PPIs and reconstructing a comprehensive PPI network of an interesting organism.     

Evolutionary changes of metabolic networks and their biosynthetic capacities

The metabolic networks of different species show a large variety in their structural design. In this work, the evolution of functional properties of metabolism in relation with metabolic network structure is investigated. The metabolism of ancestral species is inferred from the metabolism of contemporary species using a Bayesian network model for metabolism evolution. Subsequently, these networks are analysed with the recently developed method of network expansion. This method allows for a structural analysis of metabolic networks as well as a quantification of network functions in terms of their synthesising capacities when they are provided with certain external resources. The evolutionary dynamics of one particular network function: the metabolic expansion of glucose is investigated.     

Criticality Is an Emergent Property of Genetic Networks that Exhibit Evolvability

Accumulating experimental evidence suggests that the gene regulatory networks of living organisms operate in the critical phase, namely, at the transition between ordered and chaotic dynamics. Such critical dynamics of the network permits the coexistence of robustness and flexibility which are necessary to ensure homeostatic stability (of a given phenotype) while allowing for switching between multiple phenotypes (network states) as occurs in development and in response to environmental change. However, the mechanisms through which genetic networks evolve such critical behavior have remained elusive. Here we present an evolutionary model in which criticality naturally emerges from the need to balance between the two essential components of evolvability: phenotype conservation and phenotype innovation under mutations. We simulated the Darwinian evolution of random Boolean networks that mutate gene regulatory interactions and grow by gene duplication. The mutating networks were subjected to selection for networks that both (i) preserve all the already acquired phenotypes (dynamical attractor states) and (ii) generate new ones. Our results show that this interplay between extending the phenotypic landscape (innovation) while conserving the existing phenotypes (conservation) suffices to cause the evolution of all the networks in a population towards criticality. Furthermore, the networks produced by this evolutionary process exhibit structures with hubs (global regulators) similar to the observed topology of real gene regulatory networks. Thus, dynamical criticality and certain elementary topological properties of gene regulatory networks can emerge as a byproduct of the evolvability of the phenotypic landscape.     

Robustness of predictions of extremely thermally stable proteins in ancient organisms

A number of studies have addressed the environmental temperatures experienced by ancient life. Computational studies using a nonhomogeneous evolution model have estimated ancestral G + C contents of ribosomal RNAs and the amino acid compositions of ancestral proteins, generating hypotheses regarding the mesophilic last universal common ancestor. In contrast, our previous study computationally reconstructed ancestral amino acid sequences of nucleoside diphosphate kinases using a homogeneous model and then empirically resurrected the ancestral proteins. The thermal stabilities of these ancestral proteins were equivalent to or greater than those of extant homologous thermophilic proteins, supporting the thermophilic universal ancestor theory. In this study, we reinferred ancestral sequences using a dataset from which hyperthermophilic sequences were excluded. We also reinferred ancestral sequences using a nonhomogeneous evolution model. The newly reconstructed ancestral proteins are still thermally stable, further supporting the hypothesis that the ancient organisms contained thermally stable proteins and therefore that they were thermophilic.     

Linear Motif-Mediated Interactions Have Contributed to the Evolution of Modularity in Complex Protein Interaction Networks

The modular architecture of protein-protein interaction (PPI) networks is evident in diverse species with a wide range of complexity. However, the molecular components that lead to the evolution of modularity in PPI networks have not been clearly identified. Here, we show that weak domain-linear motif interactions (DLIs) are more likely to connect different biological modules than strong domain-domain interactions (DDIs). This molecular division of labor is essential for the evolution of modularity in the complex PPI networks of diverse eukaryotic species. In particular, DLIs may compensate for the reduction in module boundaries that originate from increased connections between different modules in complex PPI networks. In addition, we show that the identification of biological modules can be greatly improved by including molecular characteristics of protein interactions. Our findings suggest that transient interactions have played a unique role in shaping the architecture and modularity of biological networks over the course of evolution.     

In search of the biological significance of modular structures in protein networks

Many complex networks such as computer and social networks exhibit modular structures, where links between nodes are much denser within modules than between modules. It is widely believed that cellular networks are also modular, reflecting the relative independence and coherence of different functional units in a cell. While many authors have claimed that observations from the yeast protein–protein interaction (PPI) network support the above hypothesis, the observed structural modularity may be an artifact because the current PPI data include interactions inferred from protein complexes through approaches that create modules (e.g., assigning pairwise interactions among all proteins in a complex). Here we analyze the yeast PPI network including protein complexes (PIC network) and excluding complexes (PEC network). We find that both PIC and PEC networks show a significantly greater structural modularity than that of randomly rewired networks. Nonetheless, there is little evidence that the structural modules correspond to functional units, particularly in the PEC network. More disturbingly, there is no evolutionary conservation among yeast, fly, and nematode modules at either the whole-module or protein-pair level. Neither is there a correlation between the evolutionary or phylogenetic conservation of a protein and the extent of its participation in various modules. Using computer simulation, we demonstrate that a higher-than-expected modularity can arise during network growth through a simple model of gene duplication, without natural selection for modularity. Taken together, our results suggest the intriguing possibility that the structural modules in the PPI network originated as an evolutionary byproduct without biological significance.     

A network synthesis model for generating protein interaction network families

In this work, we introduce a novel network synthesis model that can generate families of evolutionarily related synthetic protein-protein interaction (PPI) networks. Given an ancestral network, the proposed model generates the network family according to a hypothetical phylogenetic tree, where the descendant networks are obtained through duplication and divergence of their ancestors, followed by network growth using network evolution models. We demonstrate that this network synthesis model can effectively create synthetic networks whose internal and cross-network properties closely resemble those of real PPI networks. The proposed model can serve as an effective framework for generating comprehensive benchmark datasets that can be used for reliable performance assessment of comparative network analysis algorithms. Using this model, we constructed a large-scale network alignment benchmark, called NAPAbench, and evaluated the performance of several representative network alignment algorithms. Our analysis clearly shows the relative performance of the leading network algorithms, with their respective advantages and disadvantages. The algorithm and source code of the network synthesis model and the network alignment benchmark NAPAbench are publicly available at http://www.ece.tamu.edu/bjyoon/NAPAbench/.     

Structure versus time in the evolutionary diversification of avian carotenoid metabolic networks

Historical associations of genes and proteins are thought to delineate pathways available to subsequent evolution; however, the effects of past functional involvements on contemporary evolution are rarely quantified. Here, we examined the extent to which the structure of a carotenoid enzymatic network persists in avian evolution. Specifically, we tested whether the evolution of carotenoid networks was most concordant with phylogenetically structured expansion from core reactions of common ancestors or with subsampling of biochemical pathway modules from an ancestral network. We compared structural and historical associations in 467 carotenoid networks of extant and ancestral species and uncovered the overwhelming effect of pre‐existing metabolic network structure on carotenoid diversification over the last 50 million years of avian evolution. Over evolutionary time, birds repeatedly subsampled and recombined conserved biochemical modules, which likely maintained the overall structure of the carotenoid metabolic network during avian evolution. These findings explain the recurrent convergence of evolutionary distant species in carotenoid metabolism and weak phylogenetic signal in avian carotenoid evolution. Remarkable retention of an ancient metabolic structure throughout extensive and prolonged ecological diversification in avian carotenoid metabolism illustrates a fundamental requirement of organismal evolution – historical continuity of a deterministic network that links past and present functional associations of its components.     

The evolution of molecular genetic pathways and networks

There is growing interest in the evolutionary dynamics of molecular genetic pathways and networks, and the extent to which the molecular evolution of a gene depends on its position within a pathway or network, as well as over-all network topology. Investigations on the relationships between network organization, topological architecture and evolutionary dynamics provide intriguing hints as to how networks evolve. Recent studies also suggest that genetic pathway and network structures may influence the action of evolutionary forces, and may play a role in maintaining phenotypic robustness in organisms.     

Discovering functional interaction patterns in protein-protein interaction networks

Background  

In recent years, a considerable amount of research effort has been directed to the analysis of biological networks with the availability of genome-scale networks of genes and/or proteins of an increasing number of organisms. A protein-protein interaction (PPI) network is a particular biological network which represents physical interactions between pairs of proteins of an organism. Major research on PPI networks has focused on understanding the topological organization of PPI networks, evolution of PPI networks and identification of conserved subnetworks across different species, discovery of modules of interaction, use of PPI networks for functional annotation of uncharacterized proteins, and improvement of the accuracy of currently available networks.     

Network Dynamics Contribute to Structure: Nestedness in Mutualistic Networks

Both ecological and evolutionary timescales are of importance when considering an ecological system; population dynamics affect the evolution of species traits, and vice versa. Recently, these two timescales have been used to explain structural patterns in host-parasite networks, where the evolution of the manner in which species balance the use of their resources in interactions with each other was examined. One of these patterns was nestedness, in which the set of parasite species within a particular host forms a subset of those within a more species-rich host. Patterns of both nestedness and anti-nestedness have been observed significantly more often than expected due to chance in host-parasite networks. In contrast, mutualistic networks tend to display a significant degree of nestedness, but are rarely anti-nested. Within networks with different interaction types, therefore, there appears to be a feature promoting non-random structural patterns, such as nestedness and anti-nestedness, depending on the interaction types involved. Here, we invoke the co-evolution of species trait-values when allocating resources to interactions to explain the structural pattern of nestedness in a mutualistic community. We look at a bipartite, multi-species system, in which the strength of an interaction between two species is determined by the resources that each species invests in that relationship. We then analyze the evolution of these interactions using adaptive dynamics. We found that the evolution of these interactions, reflecting the trade-off of resources, could be used to accurately predict that nestedness occurs significantly more often than expect due to chance alone in a mutualistic network. This complements previous results applying the same concept to an antagonistic network. We conclude that population dynamics and resource trade-offs could be important promoters of structural patterns in ecological networks of different types.     

Functional evolution of the yeast protein interaction network

Protein interactions are central to most biological processes. We investigated the dynamics of emergence of the protein interaction network of Saccharomyces cerevisiae by mapping origins of proteins on an evolutionary tree. We demonstrate that evolutionary periods are characterized by distinct connectivity levels of the emerging proteins. We found that the most-connected group of proteins dates to the eukaryotic radiation, and the more ancient group of pre-eukaryotic proteins is less connected. We show that functional classes have different average connectivity levels and that the time of emergence of these functional classes parallels the observed connectivity variation in evolution. We take these findings as evidence that the evolution of function might be the reason for the differences in connectivity throughout evolutionary time. We propose that the understanding of the mechanisms that generate the scale-free protein interaction network, and possibly other biological networks, requires consideration of protein function.     

Evolutionary Biosemiotics and Multilevel Construction Networks

In contrast to the traditional relational semiotics, biosemiotics decisively deviates towards dynamical aspects of signs at the evolutionary and developmental time scales. The analysis of sign dynamics requires constructivism (in a broad sense) to explain how new components such as subagents, sensors, effectors, and interpretation networks are produced by developing and evolving organisms. Semiotic networks that include signs, tools, and subagents are multilevel, and this feature supports the plasticity, robustness, and evolvability of organisms. The origin of life is described here as the emergence of simple self-constructing semiotic networks that progressively increased the diversity of their components and relations. Primitive organisms have no capacity to classify and track objects; thus, we need to admit the existence of proto-signs that directly regulate activities of agents without being associated with objects. However, object recognition and handling became possible in eukaryotic species with the development of extensive rewritable epigenetic memory as well as sensorial and effector capacities. Semiotic networks are based on sequential and recursive construction, where each step produces components (i.e., agents, scaffolds, signs, and resources) that are needed for the following steps of construction. Construction is not limited to repair and reproduction of what already exists or is unambiguously encoded, it also includes production of new components and behaviors via learning and evolution. A special case is the emergence of new levels of organization known as metasystem transition. Multilevel semiotic networks reshape the phenotype of organisms by combining a mosaic of features developed via learning and evolution of cooperating and/or conflicting subagents.     

Geometric De-noising of Protein-Protein Interaction Networks

Understanding complex networks of protein-protein interactions (PPIs) is one of the foremost challenges of the post-genomic era. Due to the recent advances in experimental bio-technology, including yeast-2-hybrid (Y2H), tandem affinity purification (TAP) and other high-throughput methods for protein-protein interaction (PPI) detection, huge amounts of PPI network data are becoming available. Of major concern, however, are the levels of noise and incompleteness. For example, for Y2H screens, it is thought that the false positive rate could be as high as 64%, and the false negative rate may range from 43% to 71%. TAP experiments are believed to have comparable levels of noise.We present a novel technique to assess the confidence levels of interactions in PPI networks obtained from experimental studies. We use it for predicting new interactions and thus for guiding future biological experiments. This technique is the first to utilize currently the best fitting network model for PPI networks, geometric graphs. Our approach achieves specificity of 85% and sensitivity of 90%. We use it to assign confidence scores to physical protein-protein interactions in the human PPI network downloaded from BioGRID. Using our approach, we predict 251 interactions in the human PPI network, a statistically significant fraction of which correspond to protein pairs sharing common GO terms. Moreover, we validate a statistically significant portion of our predicted interactions in the HPRD database and the newer release of BioGRID. The data and Matlab code implementing the methods are freely available from the web site: http://www.kuchaev.com/Denoising.