This Article OPEN ACCESS ARTICLE Full Text (PDF) Supplemental Research Data All Versions of this Article: gr.5235706v1 16/9/1169    most recent Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Flannick, J. Articles by Batzoglou, S. Search for Related Content PubMed PubMed Citation Articles by Flannick, J. Articles by Batzoglou, S. Social Bookmarking                   What's this?

Methods

Græmlin: General and robust alignment of multiple large interaction networks

¹Department of Computer Science, Stanford University, Stanford, California 94305, USA; ²Department of Developmental Biology, Stanford University, Stanford, California 94305, USA; ³Department of Electrical Engineering, Stanford University, Stanford, California 94305, USA

The recent proliferation of protein interaction networks has motivated research into network alignment: the cross-species comparison of conserved functional modules. Previous studies have laid the foundations for such comparisons and demonstrated their power on a select set of sparse interaction networks. Recently, however, new computational techniques have produced hundreds of predicted interaction networks with interconnection densities that push existing alignment algorithms to their limits. To find conserved functional modules in these new networks, we have developed Græmlin, the first algorithm capable of scalable multiple network alignment. Græmlin’s explicit model of functional evolution allows both the generalization of existing alignment scoring schemes and the location of conserved network topologies other than protein complexes and metabolic pathways. To assess Græmlin’s performance, we have developed the first quantitative benchmarks for network alignment, which allow comparisons of algorithms in terms of their ability to recapitulate the KEGG database of conserved functional modules. We find that Græmlin achieves substantial scalability gains over previous methods while improving sensitivity.

⁵ Corresponding author.

E-mail serafim{at}cs.stanford.edu; fax (650) 725-1449.

Article is online at http://www.genome.org/cgi/doi/10.1101/gr.5235706

[Supplemental material is available online at www.genome.org. Græmlin is available at http://graemlin.stanford.edu, and source code is available under the GNU Public License.]

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?

This article has been cited by other articles:

				M. T. Dittrich, G. W. Klau, A. Rosenwald, T. Dandekar, and T. Muller Identifying functional modules in protein-protein interaction networks: an integrated exact approach Bioinformatics, July 1, 2008; 24(13): i223 - i231. [Abstract] [PDF]

				M. Kalaev, M. Smoot, T. Ideker, and R. Sharan NetworkBLAST: comparative analysis of protein networks Bioinformatics, February 15, 2008; 24(4): 594 - 596. [Abstract] [Full Text] [PDF]

				J. W. Pinney, G. D. Amoutzias, M. Rattray, and D. L. Robertson Reconstruction of ancestral protein interaction networks for the bZIP transcription factors PNAS, December 18, 2007; 104(51): 20449 - 20453. [Abstract] [Full Text] [PDF]

				B. S. Srinivasan, N. H. Shah, J. A. Flannick, E. Abeliuk, A. F. Novak, and S. Batzoglou Current progress in network research: toward reference networks for key model organisms Brief Bioinform, September 1, 2007; 8(5): 318 - 332. [Abstract] [Full Text] [PDF]

				J. Dutkowski and J. Tiuryn Identification of functional modules from conserved ancestral protein protein interactions Bioinformatics, July 1, 2007; 23(13): i149 - i158. [Abstract] [Full Text] [PDF]

				Y. Huang, H. Li, H. Hu, X. Yan, M. S. Waterman, H. Huang, and X. J. Zhou Systematic discovery of functional modules and context-specific functional annotation of human genome Bioinformatics, July 1, 2007; 23(13): i222 - i229. [Abstract] [Full Text] [PDF]