{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:57:34Z","timestamp":1773392254509,"version":"3.50.1"},"reference-count":29,"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: Global many-to-many alignment of biological networks has been a central problem in comparative biological network studies. Given a set of biological interaction networks, the informal goal is to group together related nodes. For the case of protein\u2013protein interaction networks, such groups are expected to form clusters of functionally orthologous proteins. Construction of such clusters for networks from different species may prove useful in determining evolutionary relationships, in predicting the functions of proteins with unknown functions and in verifying those with estimated functions.<\/jats:p>\n               <jats:p>Results: A central informal objective in constructing clusters of orthologous proteins is to guarantee that each cluster is composed of members with high homological similarity, usually determined via sequence similarities, and that the interactions of the proteins involved in the same cluster are conserved across the input networks. We provide a formal definition of the global many-to-many alignment of multiple protein\u2013protein interaction networks that captures this informal objective. We show the computational intractability of the suggested definition. We provide a heuristic method based on backbone extraction and merge strategy (BEAMS) for the problem. We finally show, through experiments based on biological significance tests, that the proposed BEAMS algorithm performs better than the state-of-the-art approaches. Furthermore, the computational burden of the BEAMS algorithm in terms of execution speed and memory requirements is more reasonable than the competing algorithms.<\/jats:p>\n               <jats:p>Availability and implementation: Supplementary material including code implementations in LEDA C++, experimental data and the results are available at http:\/\/webprs.khas.edu.tr\/\u223ccesim\/BEAMS.tar.gz.<\/jats:p>\n               <jats:p>Contacts: \u00a0ferhat.alkan@stu.khas.edu.tr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt713","type":"journal-article","created":{"date-parts":[[2013,12,13]],"date-time":"2013-12-13T02:10:14Z","timestamp":1386900614000},"page":"531-539","source":"Crossref","is-referenced-by-count":67,"title":["BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks"],"prefix":"10.1093","volume":"30","author":[{"given":"Ferhat","family":"Alkan","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083, Turkey"}]},{"given":"Cesim","family":"Erten","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083, Turkey"}]}],"member":"286","published-online":{"date-parts":[[2013,12,11]]},"reference":[{"key":"2023012710425307000_btt713-B1","doi-asserted-by":"crossref","first-page":"i145","DOI":"10.1093\/bioinformatics\/btt235","article-title":"Campways: constrained alignment framework for the comparative analysis of a pair of metabolic pathways","volume":"29","author":"Abaka","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012710425307000_btt713-B2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1038\/nature01511","article-title":"Mass spectrometry-based proteomics","volume":"422","author":"Aebersold","year":"2003","journal-title":"Nature"},{"key":"2023012710425307000_btt713-B3","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","article-title":"Spinal: scalable protein interaction network alignment","volume":"29","author":"Alada\u011f","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012710425307000_btt713-B4","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1093\/nar\/gkp878","article-title":"The intact molecular interaction database in 2010","volume":"38","author":"Aranda","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene Ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023012710425307000_btt713-B6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1089\/cmb.2010.0280","article-title":"Submap: aligning metabolic pathways with subnetwork mappings","volume":"18","author":"Ay","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012710425307000_btt713-B7","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1093\/nar\/gkm1001","article-title":"The biogrid interaction database: 2008 update","volume":"36","author":"Breitkreutz","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B8","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1093\/nar\/gkp983","article-title":"Mint, the molecular interaction database: 2009 update","volume":"38","author":"Ceol","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B9","first-page":"123","article-title":"Local optimization for global alignment of protein interaction networks","volume":"2010","author":"Chindelevitch","year":"2010","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012710425307000_btt713-B10","doi-asserted-by":"crossref","first-page":"12980","DOI":"10.1073\/pnas.91.26.12980","article-title":"Interaction mating reveals binary and ternary connections between drosophila cell cycle regulators","volume":"91","author":"Finley","year":"1994","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012710425307000_btt713-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":"2023012710425307000_btt713-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":"2023012710425307000_btt713-B13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-2836(02)01038-0","article-title":"Co-evolutionary analysis reveals insights into protein-protein interactions","volume":"324","author":"Goh","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023012710425307000_btt713-B14","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1093\/nar\/gkn828","article-title":"Ensembl 2009","volume":"37","author":"Hubbard","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B15","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":"J. Comput. Biol."},{"key":"2023012710425307000_btt713-B16","doi-asserted-by":"crossref","first-page":"83","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 Res."},{"key":"2023012710425307000_btt713-B17","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1093\/nar\/gkn892","article-title":"Human protein reference database-2009 update","volume":"37","author":"Keshava Prasad","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B18","first-page":"22.1","article-title":"Artificial intelligence search algorithms","volume-title":"Algorithms and Theory of Computation Handbook","author":"Korf","year":"2010"},{"key":"2023012710425307000_btt713-B19","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":"2023012710425307000_btt713-B20","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":"2023012710425307000_btt713-B21","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1126\/science.285.5428.751","article-title":"Detecting protein function and protein-protein interactions from genome sequences","volume":"285","author":"Marcotte","year":"1999","journal-title":"Science"},{"key":"2023012710425307000_btt713-B22","volume-title":"Leda: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn","year":"1999"},{"key":"2023012710425307000_btt713-B23","doi-asserted-by":"crossref","first-page":"295","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 Res."},{"key":"2023012710425307000_btt713-B24","doi-asserted-by":"crossref","first-page":"e41474","DOI":"10.1371\/journal.pone.0041474","article-title":"A network synthesis model for generating protein interaction network families","volume":"7","author":"Sahraeian","year":"2012","journal-title":"PLoS One"},{"key":"2023012710425307000_btt713-B25","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":"2023012710425307000_btt713-B26","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1093\/nar\/gkh086","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012710425307000_btt713-B27","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":"2023012710425307000_btt713-B28","first-page":"303","article-title":"Global alignment of multiple protein interaction networks","volume":"2008","author":"Singh","year":"2008","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012710425307000_btt713-B29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12033-007-0069-2","article-title":"Computational prediction of protein-protein interactions","volume":"38","author":"Skrabanek","year":"2008","journal-title":"Mol. Biotechnol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/531\/48917990\/bioinformatics_30_4_531.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/531\/48917990\/bioinformatics_30_4_531.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T10:59:58Z","timestamp":1674817198000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/4\/531\/204373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,11]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt713","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,11]]}}}