{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T06:55:30Z","timestamp":1778309730170,"version":"3.51.4"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Owing to recent advancements in high-throughput technologies, protein\u2013protein interaction networks of more and more species become available in public databases. The question of how to identify functionally conserved proteins across species attracts a lot of attention in computational biology. Network alignments provide a systematic way to solve this problem. However, most existing alignment tools encounter limitations in tackling this problem. Therefore, the demand for faster and more efficient alignment tools is growing.<\/jats:p>\n               <jats:p>Results: We present a fast and accurate algorithm, NetCoffee, which allows to find a global alignment of multiple protein\u2013protein interaction networks. NetCoffee searches for a global alignment by maximizing a target function using simulated annealing on a set of weighted bipartite graphs that are constructed using a triplet approach similar to T-Coffee. To assess its performance, NetCoffee was applied to four real datasets. Our results suggest that NetCoffee remedies several limitations of previous algorithms, outperforms all existing alignment tools in terms of speed and nevertheless identifies biologically meaningful alignments.<\/jats:p>\n               <jats:p>Availability: The source code and data are freely available for download under the GNU GPL v3 license at https:\/\/code.google.com\/p\/netcoffee\/.<\/jats:p>\n               <jats:p>Contact: Jialu.Hu@fu-berlin.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt715","type":"journal-article","created":{"date-parts":[[2013,12,15]],"date-time":"2013-12-15T01:09:42Z","timestamp":1387069782000},"page":"540-548","source":"Crossref","is-referenced-by-count":59,"title":["NetCoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks"],"prefix":"10.1093","volume":"30","author":[{"given":"Jialu","family":"Hu","sequence":"first","affiliation":[{"name":"1 Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany and 2Max Planck Institute for Molecular Genetics, Ihnestrasse 63-73, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Birte","family":"Kehr","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany and 2Max Planck Institute for Molecular Genetics, Ihnestrasse 63-73, 14195 Berlin, Germany"},{"name":"1 Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany and 2Max Planck Institute for Molecular Genetics, Ihnestrasse 63-73, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany and 2Max Planck Institute for Molecular Genetics, Ihnestrasse 63-73, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2013,12,13]]},"reference":[{"key":"2023012710422098800_btt715-B1","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","article-title":"Spinal: scalable protein interaction network alignment","volume":"29","author":"Aladag","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023012710422098800_btt715-B3","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1101\/gr.4526006","article-title":"Systematic identification of functional orthologs based on protein network comparison","volume":"16","author":"Bandyopadhyay","year":"2006","journal-title":"Genome Res."},{"key":"2023012710422098800_btt715-B4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"2023012710422098800_btt715-B5","doi-asserted-by":"crossref","first-page":"3710","DOI":"10.1093\/bioinformatics\/bth456","article-title":"Go::termfinderopen source software for accessing gene ontology information and finding significantly enriched gene ontology terms associated with a list of genes","volume":"20","author":"Boyle","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B6","volume-title":"Inferring Protein Function from Sequence","author":"Brutlag","year":"2008"},{"key":"2023012710422098800_btt715-B7","doi-asserted-by":"crossref","first-page":"D262","DOI":"10.1093\/nar\/gkh021","article-title":"The gene ontology annotation (GOA) database: sharing knowledge in Uniprot with gene ontology","volume":"32","author":"Camon","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012710422098800_btt715-B8","first-page":"123","article-title":"Local optimization for global alignment of protein interaction networks","volume":"10","author":"Chindelevitch","year":"2010","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012710422098800_btt715-B9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.entcs.2011.06.003","article-title":"LEMON \u2013 an open source C++ graph template library","volume":"264","author":"Dezs","year":"2011","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"2023012710422098800_btt715-B10","first-page":"225","article-title":"Lagrangian relaxation applied to sparse global network alignment","volume-title":"Pattern Recognition in Bioinformatics, volume 7036 of Lecture Notes in Computer Science","author":"El-Kebir","year":"2011"},{"key":"2023012710422098800_btt715-B11","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1101\/gr.5235706","article-title":"Graemlin: general and robust alignment of multiple large interaction networks","volume":"16","author":"Flannick","year":"2006","journal-title":"Genome Res."},{"key":"2023012710422098800_btt715-B12","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1089\/cmb.2009.0099","article-title":"Automatic parameter learning for multiple local network alignment","volume":"16","author":"Flannick","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012710422098800_btt715-B13","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-12727-5_4","article-title":"Efficient algorithms for finding maximal matching in graphs","volume-title":"Proceedings of the 8th Colloquium on Trees in Algebra and Programming","author":"Galil","year":"1983"},{"key":"2023012710422098800_btt715-B14","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1038\/415180a","article-title":"Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry","volume":"415","author":"Ho","year":"2002","journal-title":"Nature"},{"key":"2023012710422098800_btt715-B15","doi-asserted-by":"crossref","first-page":"4569","DOI":"10.1073\/pnas.061034498","article-title":"A comprehensive two-hybrid analysis to explore the yeast protein interactome","volume":"98","author":"Ito","year":"2001","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2023012710422098800_btt715-B16","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1093\/bioinformatics\/btm630","article-title":"Networkblast: comparative analysis of protein networks","volume":"24","author":"Kalaev","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B17","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1089\/cmb.2009.0136","article-title":"Fast and accurate alignment of multiple protein networks","volume":"16","author":"Kalaev","year":"2009","journal-title":"Journal of Computational Biology"},{"key":"2023012710422098800_btt715-B18","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012710422098800_btt715-B19","doi-asserted-by":"crossref","first-page":"W83","DOI":"10.1093\/nar\/gkh411","article-title":"PathBLAST: a tool for alignment of protein interaction networks","volume":"32","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Research"},{"key":"2023012710422098800_btt715-B20","doi-asserted-by":"crossref","first-page":"D841","DOI":"10.1093\/nar\/gkr1088","article-title":"The intact molecular interaction database in 2012","volume":"40","author":"Kerrien","year":"2012","journal-title":"Nucleic Acids Research"},{"key":"2023012710422098800_btt715-B21","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023012710422098800_btt715-B22","first-page":"995","article-title":"Pairwise local alignment of protein interaction networks guided by models of evolution","volume-title":"Research in Computational Molecular Biology, volume 3500 of Lecture Notes in Computer Science","author":"Koyut\u00fcrk","year":"2005"},{"key":"2023012710422098800_btt715-B23","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B24","doi-asserted-by":"crossref","first-page":"13057","DOI":"10.1073\/pnas.94.24.13057","article-title":"Yeast microarrays for genome wide parallel genetic and gene expression analysis","volume":"94","author":"Lashkari","year":"1997","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2023012710422098800_btt715-B25","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"IsoRankN: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B26","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of State Calculations by Fast Computing Machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"The Journal of Chemical Physics"},{"key":"2023012710422098800_btt715-B27","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","article-title":"Dialign 2: improvement of the segment-to-segment approach to multiple sequence alignment","volume":"15","author":"Morgenstern","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B28","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"Journal of Molecular Biology"},{"key":"2023012710422098800_btt715-B29","doi-asserted-by":"crossref","first-page":"D476","DOI":"10.1093\/nar\/gki107","article-title":"Inparanoid: a comprehensive database of eukaryotic orthologs","volume":"33","author":"O\u2019Brien","year":"2005","journal-title":"Nucleic Acids Research"},{"key":"2023012710422098800_btt715-B30","doi-asserted-by":"crossref","first-page":"W157","DOI":"10.1093\/nar\/gks446","article-title":"NetAligner\u2013a network alignment server to compare complexes, pathways and whole interactomes","volume":"40","author":"Pache","year":"2012","journal-title":"Nucleic Acids Research."},{"key":"2023012710422098800_btt715-B31","doi-asserted-by":"crossref","first-page":"D295","DOI":"10.1093\/nar\/gkq1234","article-title":"IsoBase: a database of functionally related proteins across PPI networks","volume":"39","author":"Park","year":"2011","journal-title":"Nucleic Acids Research"},{"key":"2023012710422098800_btt715-B32","doi-asserted-by":"crossref","first-page":"3105","DOI":"10.1093\/bioinformatics\/bts592","article-title":"Global network alignment using multiscale spectral signatures","volume":"28","author":"Patro","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B33","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1093\/bioinformatics\/bts119","article-title":"Pinalog: a novel approach to align protein interaction networksimplications for complex detection and function prediction","volume":"28","author":"Phan","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012710422098800_btt715-B34","article-title":"On the convergence time of simulated annealing. Technical report","author":"Rajasekaran","year":"1990"},{"key":"2023012710422098800_btt715-B35","doi-asserted-by":"crossref","first-page":"e67995","DOI":"10.1371\/journal.pone.0067995","article-title":"Smetana: Accurate and scalable algorithm for probabilistic alignment of large-scale biological networks","volume":"8","author":"Sahraeian","year":"2013","journal-title":"PLoS One"},{"key":"2023012710422098800_btt715-B36","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1186\/1471-2105-7-302","article-title":"A new measure for functional similarity of gene products based on gene ontology","volume":"7","author":"Schlicker","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012710422098800_btt715-B37","doi-asserted-by":"crossref","first-page":"R33","DOI":"10.1186\/gb-2007-8-3-r33","article-title":"GOTax: investigating biological processes and biochemical activities along the taxonomic tree","volume":"8","author":"Schlicker","year":"2007","journal-title":"Genome Biol."},{"key":"2023012710422098800_btt715-B38","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012710422098800_btt715-B39","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotech."},{"key":"2023012710422098800_btt715-B40","doi-asserted-by":"crossref","first-page":"S11","DOI":"10.1186\/1471-2105-13-S3-S11","article-title":"Scalable global alignment for multiple biological networks","volume":"13","author":"Shih","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012710422098800_btt715-B41","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-71681-5_2","article-title":"Pairwise global alignment of protein interaction networks by matching neighborhood topology","volume-title":"Proceedings of the 11th annual international conference on Research in computational molecular biology","author":"Singh","year":"2007"},{"key":"2023012710422098800_btt715-B42","doi-asserted-by":"crossref","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012710422098800_btt715-B43","doi-asserted-by":"crossref","first-page":"D561","DOI":"10.1093\/nar\/gkq973","article-title":"The string database in 2011: functional interaction networks of proteins, globally integrated and scored","volume":"39","author":"Szklarczyk","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012710422098800_btt715-B44","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023012710422098800_btt715-B45","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1093\/nar\/28.1.33","article-title":"The COG database: a tool for genome-scale analysis of protein functions and evolution","volume":"28","author":"Tatusov","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023012710422098800_btt715-B46","doi-asserted-by":"crossref","first-page":"D193","DOI":"10.1093\/nar\/gkl929","article-title":"The universal protein resource (UniProt)","volume":"35","author":"Uniprot Consortium","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023012710422098800_btt715-B47","doi-asserted-by":"crossref","first-page":"D283","DOI":"10.1093\/nar\/gkq930","article-title":"OrthoDB: the hierarchical catalog of eukaryotic orthologs in 2011","volume":"39","author":"Waterhouse","year":"2011","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/540\/48915427\/bioinformatics_30_4_540.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/540\/48915427\/bioinformatics_30_4_540.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T10:58:00Z","timestamp":1674817080000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/4\/540\/204711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,13]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt715","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,2,15]]},"published":{"date-parts":[[2013,12,13]]}}}