{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:05:26Z","timestamp":1767917126226,"version":"3.49.0"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Discovering patterns in networks of protein\u2013protein interactions (PPIs) is a central problem in systems biology. Alignments between these networks aid functional understanding as they uncover important information, such as evolutionary conserved pathways, protein complexes and functional orthologs. However, the complexity of the multiple network alignment problem grows exponentially with the number of networks being aligned and designing a multiple network aligner that is both scalable and that produces biologically relevant alignments is a challenging task that has not been fully addressed. The objective of multiple network alignment is to create clusters of nodes that are evolutionarily and functionally conserved across all networks. Unfortunately, the alignment methods proposed thus far do not meet this objective as they are guided by pairwise scores that do not utilize the entire functional and evolutionary information across all networks.<\/jats:p>\n               <jats:p>Results: To overcome this weakness, we propose Fuse, a new multiple network alignment algorithm that works in two steps. First, it computes our novel protein functional similarity scores by fusing information from wiring patterns of all aligned PPI networks and sequence similarities between their proteins. This is in contrast with the previous tools that are all based on protein similarities in pairs of networks being aligned. Our comprehensive new protein similarity scores are computed by Non-negative Matrix Tri-Factorization (NMTF) method that predicts associations between proteins whose homology (from sequences) and functioning similarity (from wiring patterns) are supported by all networks. Using the five largest and most complete PPI networks from BioGRID, we show that NMTF predicts a large number protein pairs that are biologically consistent. Second, to identify clusters of aligned proteins over all networks, Fuse uses our novel maximum weight k-partite matching approximation algorithm. We compare Fuse with the state of the art multiple network aligners and show that (i) by using only sequence alignment scores, Fuse already outperforms other aligners and produces a larger number of biologically consistent clusters that cover all aligned PPI networks and (ii) using both sequence alignments and topological NMTF-predicted scores leads to the best multiple network alignments thus far.<\/jats:p>\n               <jats:p>Availability and implementation: Our dataset and software are freely available from the web site: http:\/\/bio-nets.doc.ic.ac.uk\/Fuse\/.<\/jats:p>\n               <jats:p>Contact: \u00a0natasha@imperial.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv731","type":"journal-article","created":{"date-parts":[[2015,12,15]],"date-time":"2015-12-15T02:54:41Z","timestamp":1450148081000},"page":"1195-1203","source":"Crossref","is-referenced-by-count":41,"title":["Fuse: multiple network alignment via data fusion"],"prefix":"10.1093","volume":"32","author":[{"given":"Vladimir","family":"Gligorijevi\u0107","sequence":"first","affiliation":[{"name":"Department of Computing, Imperial College London, London SW7 2AZ, UK"}]},{"given":"No\u00ebl","family":"Malod-Dognin","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, London SW7 2AZ, UK"}]},{"given":"Nata\u0161a","family":"Pr\u017eulj","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, London SW7 2AZ, UK"}]}],"member":"286","published-online":{"date-parts":[[2015,12,14]]},"reference":[{"key":"2023020111594286500_btv731-B1","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1093\/bioinformatics\/btt713","article-title":"Beams: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks","volume":"30","author":"Alkan","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020111594286500_btv731-B2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023020111594286500_btv731-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":"2023020111594286500_btv731-B4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications. Vol. 6","author":"Bondy","year":"1976"},{"key":"2023020111594286500_btv731-B5","doi-asserted-by":"crossref","first-page":"D816","DOI":"10.1093\/nar\/gks1158","article-title":"The BioGRID interaction database: 2013 update","volume":"41","author":"Chatr-Aryamontri","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023020111594286500_btv731-B6","doi-asserted-by":"crossref","first-page":"2351","DOI":"10.1093\/bioinformatics\/btu307","article-title":"A comparison of algorithms for the pairwise alignment of biological networks","volume":"30","author":"Clark","year":"2014","journal-title":"Bioinformatics."},{"key":"2023020111594286500_btv731-B7","author":"Cook","year":"1971"},{"key":"2023020111594286500_btv731-B8","author":"Ding","year":"2005"},{"key":"2023020111594286500_btv731-B9","doi-asserted-by":"crossref","DOI":"10.1145\/1150402.1150420","article-title":"Orthogonal nonnegative matrix t-factorizations for clustering","author":"Ding","year":"2006"},{"key":"2023020111594286500_btv731-B10","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":"2023020111594286500_btv731-B11","doi-asserted-by":"crossref","first-page":"e184","DOI":"10.1093\/bioinformatics\/btl230","article-title":"Predicting the prognosis of breast cancer by integrating clinical and microarray data with Bayesian networks","volume":"22","author":"Gevaert","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020111594286500_btv731-B12","doi-asserted-by":"crossref","first-page":"i594","DOI":"10.1093\/bioinformatics\/btu470","article-title":"Integration of molecular network data reconstruct gene ontology","volume":"30","author":"Gligorijevi\u0107","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020111594286500_btv731-B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00021","article-title":"Approximation algorithms for some graph partitioning problems","volume":"4","author":"He","year":"2000","journal-title":"J. Graph Algorithms Appl"},{"key":"2023020111594286500_btv731-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":"2023020111594286500_btv731-B15","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1093\/bioinformatics\/btt715","article-title":"NetCoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks","volume":"30","author":"Hu","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020111594286500_btv731-B16","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1073\/pnas.97.3.1143","article-title":"Toward a protein-protein interaction map of the budding yeast: a comprehensive system to examine two-hybrid interactions in all possible combinations between the yeast proteins","volume":"97","author":"Ito","year":"2000","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020111594286500_btv731-B17","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1752-0509-9-S1-S7","article-title":"Accurate multiple network alignment through context-sensitive random walk","volume":"9","author":"Jeong","year":"2015","journal-title":"BMC Syst. Biol"},{"key":"2023020111594286500_btv731-B18","volume-title":"Principal Component Analysis","author":"Jolliffe","year":"2005"},{"key":"2023020111594286500_btv731-B19","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":"2023020111594286500_btv731-B20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume":"6","author":"Karp","year":"1972","journal-title":"Complexity Comput. Comput"},{"key":"2023020111594286500_btv731-B21","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":"2023020111594286500_btv731-B22","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 Res"},{"key":"2023020111594286500_btv731-B23","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/MC.2009.263","article-title":"Matrix factorization techniques for recommender systems","volume":"42","author":"Koren","year":"2009","journal-title":"Computer"},{"key":"2023020111594286500_btv731-B24","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","article-title":"Pairwise alignment of protein interaction networks","volume":"13","author":"Koyut\u00fcrk","year":"2006","journal-title":"J. Comput. Biol"},{"key":"2023020111594286500_btv731-B25","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","article-title":"Topological network alignment uncovers biological function and phylogeny","volume":"7","author":"Kuchaiev","year":"2010","journal-title":"J. R. Soc. Interface"},{"key":"2023020111594286500_btv731-B26","doi-asserted-by":"crossref","first-page":"2626","DOI":"10.1093\/bioinformatics\/bth294","article-title":"A statistical framework for genomic data fusion","volume":"20","author":"Lanckriet","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020111594286500_btv731-B27","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":"2023020111594286500_btv731-B28","author":"Lov\u00e1sz","year":"1986"},{"key":"2023020111594286500_btv731-B29","doi-asserted-by":"crossref","first-page":"D54","DOI":"10.1093\/nar\/gki031","article-title":"Entrez gene: gene-centered information at ncbi","volume":"33","author":"Maglott","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023020111594286500_btv731-B30","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1038\/nrg3552","article-title":"Integrative approaches for finding modular structure in biological networks","volume":"14","author":"Mitra","year":"2013","journal-title":"Nat. Rev. Genet"},{"key":"2023020111594286500_btv731-B31","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":"J. Mol. Biol"},{"key":"2023020111594286500_btv731-B32","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"2023020111594286500_btv731-B33","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/bies.201000044","article-title":"Protein-protein interactions: making sense of networks via graph-theoretic modeling","volume":"33","author":"Pr\u017eulj","year":"2011","journal-title":"Bioessays"},{"key":"2023020111594286500_btv731-B34","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1089\/cmb.2014.0247","article-title":"Node handprinting: a scalable and accurate algorithm for aligning multiple biological networks","volume":"22","author":"Radu","year":"2015","journal-title":"J. Comput. Biol."},{"key":"2023020111594286500_btv731-B35","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1038\/nrg3574","article-title":"High-resolution network biology: connecting sequence with function","volume":"14","author":"Ryan","year":"2013","journal-title":"Nat. Rev. Genet."},{"key":"2023020111594286500_btv731-B36","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":"2023020111594286500_btv731-B37","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":"2023020111594286500_btv731-B38","first-page":"16","volume-title":"Research in Computational Molecular Biology, Volume 4453 of Lecture Notes in Computer Science","author":"Singh","year":"2007"},{"key":"2023020111594286500_btv731-B39","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":"2023020111594286500_btv731-B40","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/35001009","article-title":"A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae","volume":"403","author":"Uetz","year":"2000","journal-title":"Nature"},{"key":"2023020111594286500_btv731-B41","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1126\/science.1116804","article-title":"Herpesviral protein networks and their interaction with the human proteome","volume":"311","author":"Uetz","year":"2006","journal-title":"Science"},{"key":"2023020111594286500_btv731-B42","first-page":"1","volume-title":"SDM","author":"Wang","year":"2008"},{"key":"2023020111594286500_btv731-B43","first-page":"279","author":"Wang","year":"2011"},{"key":"2023020111594286500_btv731-B44","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1089\/cmb.2012.0273","article-title":"Predicting protein-protein interactions from multimodal biological data sources via nonnegative matrix tri-factorization","volume":"20","author":"Wang","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023020111594286500_btv731-B45","doi-asserted-by":"crossref","first-page":"16","DOI":"10.4161\/sysb.29072","article-title":"Matrix factorization-based data fusion for drug-induced liver injury prediction","volume":"2","author":"\u017ditnik","year":"2014","journal-title":"Syst. Biomed"},{"key":"2023020111594286500_btv731-B46","first-page":"400","volume-title":"Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing","author":"\u017ditnik","year":"2014"},{"key":"2023020111594286500_btv731-B47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/srep03202","article-title":"Discovering disease-disease associations by fusing systems-level molecular data","volume":"3","author":"\u017ditnik","year":"2013","journal-title":"Sci. Rep"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/8\/1195\/49018364\/bioinformatics_32_8_1195.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/8\/1195\/49018364\/bioinformatics_32_8_1195.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:24:20Z","timestamp":1675290260000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/8\/1195\/1744425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,14]]},"references-count":47,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2016,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv731","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,4,15]]},"published":{"date-parts":[[2015,12,14]]}}}