Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.


Logo for

PNAS 100 (20): 11394-11399

Copyright © 2003 by the National Academy of Sciences.


Conserved pathways within bacteria and yeast as revealed by global protein network alignment

Brian P. Kelley*, Roded Sharan{dagger}, Richard M. Karp{dagger}, Taylor Sittler*, David E. Root*, Brent R. Stockwell*, and Trey Ideker*,{ddagger}

*Whitehead Institute for Biomedical Research, 9 Cambridge Center, Cambridge, MA 02142; and {dagger}International Computer Science Institute, 1947 Center Street, No. 600, Berkeley, CA 94704

Contributed by Richard M. Karp, July 25, 2003

Abstract: 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.

{ddagger} 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{at}

Abbreviation: MAPK, mitogen-activated protein kinase.

§ 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.

Modeling disease progression using dynamics of pathway connectivity.
X. Ma, L. Gao, and K. Tan (2014)
   Abstract »    Full Text »    PDF »
Retrieval, alignment, and clustering of computational models based on semantic annotations.
M. Schulz, F. Krause, N. Le Novere, E. Klipp, and W. Liebermeister (2014)
Mol Syst Biol 7, 512
   Abstract »    Full Text »    PDF »
Network-based prediction of protein function.
R. Sharan, I. Ulitsky, and R. Shamir (2014)
Mol Syst Biol 3, 88
   Abstract »    Full Text »    PDF »
Differential network biology.
T. Ideker and N. J. Krogan (2014)
Mol Syst Biol 8, 565
   Abstract »    Full Text »    PDF »
NetCoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks.
J. Hu, B. Kehr, and K. Reinert (2014)
Bioinformatics 30, 540-548
   Abstract »    Full Text »    PDF »
Optimizing a global alignment of protein interaction networks.
L. Chindelevitch, C.-Y. Ma, C.-S. Liao, and B. Berger (2013)
Bioinformatics 29, 2765-2773
   Abstract »    Full Text »    PDF »
NETAL: a new graph-based method for global alignment of protein-protein interaction networks.
B. Neyshabur, A. Khadem, S. Hashemifar, and S. S. Arab (2013)
Bioinformatics 29, 1654-1662
   Abstract »    Full Text »    PDF »
Optimization criteria and biological process enrichment in homologous multiprotein modules.
L. Hodgkinson and R. M. Karp (2013)
PNAS 110, 10872-10877
   Abstract »    Full Text »    PDF »
Proteome-wide Prediction of Self-interacting Proteins Based on Multiple Properties.
Z. Liu, F. Guo, J. Zhang, J. Wang, L. Lu, D. Li, and F. He (2013)
Mol. Cell. Proteomics 12, 1689-1700
   Abstract »    Full Text »    PDF »
SPINAL: scalable protein interaction network alignment.
A. E. Aladag and C. Erten (2013)
Bioinformatics 29, 917-924
   Abstract »    Full Text »    PDF »
Biological network analysis: insights into structure and functions.
X. Ma and L. Gao (2012)
Briefings in Functional Genomics 11, 434-442
   Abstract »    Full Text »    PDF »
NetAligner--a network alignment server to compare complexes, pathways and whole interactomes.
R. A. Pache, A. Ceol, and P. Aloy (2012)
Nucleic Acids Res. 40, W157-W161
   Abstract »    Full Text »    PDF »
The Role of Structural Disorder in the Rewiring of Protein Interactions through Evolution.
R. Mosca, R. A. Pache, and P. Aloy (2012)
Mol. Cell. Proteomics 11, M111.014969
   Abstract »    Full Text »    PDF »
PINALOG: a novel approach to align protein interaction networks--implications for complex detection and function prediction.
H. T. T. Phan and M. J. E. Sternberg (2012)
Bioinformatics 28, 1239-1245
   Abstract »    Full Text »    PDF »
Analysis of Coevolving Gene Families Using Mutually Exclusive Orthologous Modules.
X. Zhang, M. Kupiec, U. Gophna, and T. Tuller (2011)
Genome Biol Evol 3, 413-423
   Abstract »    Full Text »    PDF »
Evolution and applications of plant pathway resources and databases.
Y. Sucaet and T. Deva (2011)
Brief Bioinform 12, 530-544
   Abstract »    Full Text »    PDF »
Systematic discovery of nonobvious human disease models through orthologous phenotypes.
K. L. McGary, T. J. Park, J. O. Woods, H. J. Cha, J. B. Wallingford, and E. M. Marcotte (2010)
PNAS 107, 6544-6549
   Abstract »    Full Text »    PDF »
Toward the dynamic interactome: it's about time.
T. M. Przytycka, M. Singh, and D. K. Slonim (2010)
Brief Bioinform
   Abstract »    Full Text »    PDF »
Functionally guided alignment of protein interaction networks for module detection.
W. Ali and C. M. Deane (2009)
Bioinformatics 25, 3166-3173
   Abstract »    Full Text »    PDF »
A complex-centric view of protein network evolution.
N. Yosef, M. Kupiec, E. Ruppin, and R. Sharan (2009)
Nucleic Acids Res. 37, e88
   Abstract »    Full Text »    PDF »
Global alignment of protein-protein interaction networks by graph matching methods.
M. Zaslavskiy, F. Bach, and J.-P. Vert (2009)
Bioinformatics 25, i259-1267
   Abstract »    Full Text »    PDF »
Domain-oriented edge-based alignment of protein interaction networks.
X. Guo and A. J. Hartemink (2009)
Bioinformatics 25, i240-1246
   Abstract »    Full Text »    PDF »
IsoRankN: spectral methods for global alignment of multiple protein networks.
C.-S. Liao, K. Lu, M. Baym, R. Singh, and B. Berger (2009)
Bioinformatics 25, i253-i258
   Abstract »    Full Text »    PDF »
Novel pathway compendium analysis elucidates mechanism of pro-angiogenic synthetic small molecule.
K. A. Wieghaus, E. P. Gianchandani, M. A. Paige, M. L. Brown, E. A. Botchwey, and J. A. Papin (2008)
Bioinformatics 24, 2384-2390
   Abstract »    Full Text »    PDF »
Global alignment of multiple protein interaction networks with application to functional orthology detection.
R. Singh, J. Xu, and B. Berger (2008)
PNAS 105, 12763-12768
   Abstract »    Full Text »    PDF »
A critical examination of stoichiometric and path-finding approaches to metabolic pathways.
F. J. Planes and J. E. Beasley (2008)
Brief Bioinform 9, 422-436
   Abstract »    Full Text »    PDF »
Identifying functional modules in protein-protein interaction networks: an integrated exact approach.
M. T. Dittrich, G. W. Klau, A. Rosenwald, T. Dandekar, and T. Muller (2008)
Bioinformatics 24, i223-i231
   Abstract »    Full Text »    PDF »
Comparative Pathway Analyzer--a web server for comparative analysis, clustering and visualization of metabolic networks in multiple organisms.
S. Oehm, D. Gilbert, A. Tauch, J. Stoye, and A. Goesmann (2008)
Nucleic Acids Res. 36, W433-W437
   Abstract »    Full Text »    PDF »
PRINCESS, a Protein Interaction Confidence Evaluation System with Multiple Data Sources.
D. Li, W. Liu, Z. Liu, J. Wang, Q. Liu, Y. Zhu, and F. He (2008)
Mol. Cell. Proteomics 7, 1043-1052
   Abstract »    Full Text »    PDF »
Tools for visually exploring biological networks.
M. Suderman and M. Hallett (2007)
Bioinformatics 23, 2651-2659
   Abstract »    Full Text »    PDF »
Current progress in network research: toward reference networks for key model organisms.
B. S. Srinivasan, N. H. Shah, J. A. Flannick, E. Abeliuk, A. F. Novak, and S. Batzoglou (2007)
Brief Bioinform 8, 318-332
   Abstract »    Full Text »    PDF »
Identification of functional modules from conserved ancestral protein protein interactions.
J. Dutkowski and J. Tiuryn (2007)
Bioinformatics 23, i149-i158
   Abstract »    Full Text »    PDF »
Systematic discovery of functional modules and context-specific functional annotation of human genome.
Y. Huang, H. Li, H. Hu, X. Yan, M. S. Waterman, H. Huang, and X. J. Zhou (2007)
Bioinformatics 23, i222-i229
   Abstract »    Full Text »    PDF »
Alignment of molecular networks by integer quadratic programming.
Z. Li, S. Zhang, Y. Wang, X.-S. Zhang, and L. Chen (2007)
Bioinformatics 23, 1631-1639
   Abstract »    Full Text »    PDF »
Transcriptional regulation of protein complexes within and across species.
K. Tan, T. Shlomi, H. Feizi, T. Ideker, and R. Sharan (2007)
PNAS 104, 1283-1288
   Abstract »    Full Text »    PDF »
Identification of conserved protein complexes based on a model of protein network evolution.
E. Hirsh and R. Sharan (2007)
Bioinformatics 23, e170-e176
   Abstract »    Full Text »    PDF »
Inferring gene regulatory networks from multiple microarray datasets.
Y. Wang, T. Joshi, X.-S. Zhang, D. Xu, and L. Chen (2006)
Bioinformatics 22, 2413-2420
   Abstract »    Full Text »    PDF »
Graemlin: General and robust alignment of multiple large interaction networks.
J. Flannick, A. Novak, B. S. Srinivasan, H. H. McAdams, and S. Batzoglou (2006)
Genome Res. 16, 1169-1181
   Abstract »    Full Text »    PDF »
Cross-species analysis of biological networks by Bayesian alignment.
J. Berg and M. Lassig (2006)
PNAS 103, 10967-10972
   Abstract »    Full Text »    PDF »
Systematic identification of functional orthologs based on protein network comparison.
S. Bandyopadhyay, R. Sharan, and T. Ideker (2006)
Genome Res. 16, 428-435
   Abstract »    Full Text »    PDF »
Molecular Interaction Maps of Bioregulatory Networks: A General Rubric for Systems Biology.
K. W. Kohn, M. I. Aladjem, J. N. Weinstein, and Y. Pommier (2006)
Mol. Biol. Cell 17, 1-13
   Abstract »    Full Text »    PDF »
Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data.
F. Boyer, A. Morgat, L. Labarre, J. Pothier, and A. Viari (2005)
Bioinformatics 21, 4209-4215
   Abstract »    Full Text »    PDF »
Alignment of metabolic pathways.
R. Y. Pinter, O. Rokhlenko, E. Yeger-Lotem, and M. Ziv-Ukelson (2005)
Bioinformatics 21, 3401-3408
   Abstract »    Full Text »    PDF »
Differential network expression during drug and stress response.
L. Cabusora, E. Sutton, A. Fulmer, and C. V. Forst (2005)
Bioinformatics 21, 2898-2905
   Abstract »    Full Text »    PDF »
Comprehensive Interaction Map of the Arabidopsis MADS Box Transcription Factors.
S. de Folter, R. G.H. Immink, M. Kieffer, L. Parenicova, S. R. Henz, D. Weigel, M. Busscher, M. Kooiker, L. Colombo, M. M. Kater, et al. (2005)
PLANT CELL 17, 1424-1433
   Abstract »    Full Text »    PDF »
Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks.
R. Christmas, I. Avila-Campillo, H. Bolouri, B. Schwikowski, M. Anderson, R. Kelley, N. Landys, C. Workman, T. Ideker, E. Cerami, et al. (2005)
Am. Assoc. Cancer Res. Educ. Book 2005, 12-16
   Full Text »    PDF »
Conserved patterns of protein interaction in multiple species.
R. Sharan, S. Suthram, R. M. Kelley, T. Kuhn, S. McCuine, P. Uetz, T. Sittler, R. M. Karp, and T. Ideker (2005)
PNAS 102, 1974-1979
   Abstract »    Full Text »    PDF »
PathBLAST: a tool for alignment of protein interaction networks.
B. P. Kelley, B. Yuan, F. Lewitter, R. Sharan, B. R. Stockwell, and T. Ideker (2004)
Nucleic Acids Res. 32, W83-W88
   Abstract »    Full Text »    PDF »
Comparative Analysis of Protein Domain Organization.
Y. Ye and A. Godzik (2004)
Genome Res. 14, 343-353
   Abstract »    Full Text »    PDF »
Systematic identification of functional orthologs based on protein network comparison.
S. Bandyopadhyay, R. Sharan, and T. Ideker (2006)
Genome Res. 16, 428-435
   Abstract »    Full Text »    PDF »

To Advertise     Find Products

Science Signaling. ISSN 1937-9145 (online), 1945-0877 (print). Pre-2008: Science's STKE. ISSN 1525-8882