We implement a strategy for aligning two protein-protein interaction networks that combines interaction topology and protein sequence similarity to identify conserved interaction pathways and complexes. Using this approach we show that the protein-protein interaction networks of two distantly related species, Saccharomyces cerevisiae and Helicobacter pylori, harbor a large complement of evolutionarily conserved pathways, and that a large number of pathways appears to have duplicated and specialized within yeast. Analysis of these findings reveals many well characterized interaction pathways as well as many unanticipated pathways, the significance of which is reinforced by their presence in the networks of both species. E volution is driven by biological variation at many levels. Mutations and rearrangements in genomic DNA lead to changes in protein structures, abundances, and modification states. Variations at the protein level, in turn, impact how proteins interact with one another, with DNA, and with small molecules to form signaling, regulatory, and metabolic networks. Changes in network organization have sweeping implications for cellular function, tissue-level responses, and the behavior and morphology of whole organisms. Gene and protein sequences have long received the most attention as metrics for evolutionary change, both because they represent a fundamental level of biological variation and because they are readily available through automated sequencing technology. However, recent technological advances also enable us to characterize networks of protein interactions. Protein interactions are crucial to cellular function both in assembling protein complexes and in signal transduction cascades. Among the most direct and systematic methods for measuring protein interactions are coimmunoprecipitation (1) and the two-hybrid system (2), which have defined large protein-protein interaction networks for organisms including Saccharomyces cerevisiae (3-5), Helicobacter pylori (6), and Caenorhabditis elegans (7). Although the quality of data from these experiments has been mixed, pooling of multiple studies and integration with other data types such as gene expression have been used to reduce the number of false-positive interactions (8). The rapid growth of protein network information raises a host of new questions in evolutionary and comparative biology. Given that protein sequences and structures are conserved in and among species, are networks of protein interactions conserved as well? Is there some minimal set of interaction pathways required for all species? Can we measure evolutionary distance at the level of network connectivity rather than at the level of DNA or protein sequence? Mounting evidence suggests that conserved protein interaction pathways indeed exist and may be ubiquitous: For example, proteins in the same pathway are typically present or absent in a genome as a group (9), and several hundred protein-protein interactions in the yeast network have also been identified for the corresponding protein orthologs in worms (10). To explore interspecies pathway conservation on a global scale, we performed a series of whole-network comparisons using the protein-protein interaction networks of the budding yeast S. cerevisiae and the bacterial pathogen H. pylori. Comparative network analysis has proven powerful in a number of related domains including metabolic pathway analysis (11-14), motif finding (15), and correlation of biological networks with gene expression (16). Here we systematically search for and prioritize conserved interaction pathways in yeast vs. bacteria, yeast vs. yeast, and yeast vs. specific ''queries'' formulated to uncover homologous mitogen-activated protein kinase (MAPK) signaling and ubiquitin ligation machinery. Methods We developed an efficient computational procedure for aligning two protein interaction networks to identify their conserved interaction pathways. § This procedure, which we named PATHBLAST because of its conceptual similarity to sequence alignment algorithms such as BLAST (17), searches for high-scoring pathway alignments involving two paths, one from each network, in which proteins of the first path ͗A, B, C, D, . . . ͘ are paired with putative homologs occurring in the same order in the second path ͗a, b, c, d, . . . ͘ (Fig. 1a) . Evolutionary variations and experimental errors in pathway structure are accommodated by allowing ''gaps'' and ''mismatches'' (see also ref. 14). A gap occurs when a protein interaction in one path skips over a protein in the other, whereas a mismatch occurs when aligned proteins do not share sequence similarity. Because of space limitations, only abbreviated methods are given in the following sections; full descriptions are available in Supporting Materials and Methods and Figs. 5 and 6, which are published as supporting information on the PNAS web site, www.pnas.org. ¶ Global Alignment and Scoring. To perform the alignment, the two networks are combined into a global alignment graph (Fig. 1b) in which each vertex represents a pair of proteins (one from each network) having at least weak sequence similarity (BLAST E value Յ 10 ) and each edge represents a conserved interaction, gap, or mismatch. A path through this graph represents a pathway alignment between the two networks. We formulate a log probability score S(P) that decomposes over the vertices v and edges e of a path P through the global alignment graph Abbreviation: MAPK, mitogen-activated protein kinase. ‡ To whom correspondence should be sent at the present address: University of California at San Diego, Department of Bioengineering, 9500 Gilman Drive, La Jolla, CA 92093. E-mail: trey@bioeng.ucsd.edu. § The term ''pathway'' has been used broadly within various molecular biological contexts to refer to biochemical reaction chains, signal transduction cascades, gene regulatory systems, or other sequences of biomolecular events. Here a pathway refers to a sequence of protein-protein interactions forming a connected path in the network. ¶ We have also explored methods for identifying conserved subnetworks as opposed to linear paths (see Fig. 7 , which is published as supporting information on the PNAS web site); choosing which approach is most desirable remains an open problem and depends on issues of computational efficiency and whether protein complexes or sequential pathways such as signal transduction or regulatory cascades are of highest interest.
Kelley et al. proposed PATHBLAST REF , that is, a procedure to align two protein interaction networks by combining interaction topology and protein sequence similarity, in order to identify conserved interaction pathways and complexes.
Conserved pathways within bacteria and yeast as revealed by global protein network alignment
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Biology Medicine