Topological network alignment uncovers biological function and phylogeny

J R Soc Interface. 2010 Sep 6;7(50):1341-54. doi: 10.1098/rsif.2010.0063. Epub 2010 Mar 17.

Abstract

Sequence comparison and alignment has had an enormous impact on our understanding of evolution, biology and disease. Comparison and alignment of biological networks will probably have a similar impact. Existing network alignments use information external to the networks, such as sequence, because no good algorithm for purely topological alignment has yet been devised. In this paper, we present a novel algorithm based solely on network topology, that can be used to align any two networks. We apply it to biological networks to produce by far the most complete topological alignments of biological networks to date. We demonstrate that both species phylogeny and detailed biological function of individual proteins can be extracted from our alignments. Topology-based alignments have the potential to provide a completely new, independent source of phylogenetic information. Our alignment of the protein-protein interaction networks of two very different species-yeast and human-indicate that even distant species share a surprising amount of network topology, suggesting broad similarities in internal cellular wiring across all life on Earth.

Publication types

  • Comparative Study
  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms*
  • Computational Biology
  • Humans
  • Models, Biological*
  • Phylogeny*
  • Proteins / chemistry*
  • Proteins / genetics
  • Proteins / metabolism
  • Saccharomyces cerevisiae / genetics*
  • Saccharomyces cerevisiae / metabolism
  • Saccharomyces cerevisiae Proteins / chemistry*
  • Saccharomyces cerevisiae Proteins / genetics
  • Saccharomyces cerevisiae Proteins / metabolism

Substances

  • Proteins
  • Saccharomyces cerevisiae Proteins