{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T13:59:35Z","timestamp":1762351175219},"reference-count":51,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Sequences and protein interaction data are of significance to understand the underlying molecular mechanism of organisms. Local network alignment is one of key systematic ways for predicting protein functions, identifying functional modules and understanding the phylogeny from these data. Most of currently existing tools, however, encounter their limitations, which are mainly concerned with scoring scheme, speed and scalability. Therefore, there are growing demands for sophisticated network evolution models and efficient local alignment algorithms.<\/jats:p>\n               <jats:p>Results: We developed a fast and scalable local network alignment tool called LocalAli for the identification of functionally conserved modules in multiple networks. In this algorithm, we firstly proposed a new framework to reconstruct the evolution history of conserved modules based on a maximum-parsimony evolutionary model. By relying on this model, LocalAli facilitates interpretation of resulting local alignments in terms of conserved modules, which have been evolved from a common ancestral module through a series of evolutionary events. A meta-heuristic method simulated annealing was used to search for the optimal or near-optimal inner nodes (i.e. ancestral modules) of the evolutionary tree. To evaluate the performance and the statistical significance, LocalAli were tested on 26 real datasets and 1040 randomly generated datasets. The results suggest that LocalAli outperforms all existing algorithms in terms of coverage, consistency and scalability, meanwhile retains a high precision in the identification of functionally coherent subnetworks.<\/jats:p>\n               <jats:p>Availability: The source code and test datasets are freely available for download under the GNU GPL v3 license at https:\/\/code.google.com\/p\/localali\/ .<\/jats:p>\n               <jats:p>Contact: \u00a0jialu.hu@fu-berlin.de or knut.reinert@fu-berlin.de .<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu652","type":"journal-article","created":{"date-parts":[[2014,10,5]],"date-time":"2014-10-05T00:35:52Z","timestamp":1412469352000},"page":"363-372","source":"Crossref","is-referenced-by-count":30,"title":["LocalAli: an evolutionary-based local alignment approach to identify functionally \n            <i>conserved<\/i>\n             modules in multiple networks"],"prefix":"10.1093","volume":"31","author":[{"given":"Jialu","family":"Hu","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Takustrasse 9, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,10,4]]},"reference":[{"key":"2023020116163790600_btu652-B1","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":"2023020116163790600_btu652-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":"2023020116163790600_btu652-B3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology. The gene ontology consortium","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat. Genet."},{"key":"2023020116163790600_btu652-B4","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":"2023020116163790600_btu652-B5","volume-title":"Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation)","author":"Chapman","year":"2007"},{"key":"2023020116163790600_btu652-B6","doi-asserted-by":"crossref","first-page":"e38107","DOI":"10.1371\/journal.pone.0038107","article-title":"Alignnemo: a local network alignment method to integrate homology and topology","volume":"7","author":"Ciriello","year":"2012","journal-title":"PLoS One"},{"key":"2023020116163790600_btu652-B7","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":"2023020116163790600_btu652-B8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.entcs.2011.06.003","article-title":"LEMON\u2013an open source C++ graph template library","volume":"264","author":"Dezs\u0151","year":"2011","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"2023020116163790600_btu652-B9","doi-asserted-by":"crossref","first-page":"i149","DOI":"10.1093\/bioinformatics\/btm194","article-title":"Identification of functional modules from conserved ancestral protein-protein interactions","volume":"23","author":"Dutkowski","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-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":"2023020116163790600_btu652-B11","doi-asserted-by":"crossref","first-page":"D136","DOI":"10.1093\/nar\/gkr1178","article-title":"The ncbi taxonomy database","volume":"40","author":"Federhen","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023020116163790600_btu652-B12","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2003","edition":"2 edn"},{"key":"2023020116163790600_btu652-B13","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","article-title":"Toward defining the course of evolution: minimum change for a specific tree topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Syst. Biol."},{"key":"2023020116163790600_btu652-B14","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":"2023020116163790600_btu652-B15","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":"2023020116163790600_btu652-B16","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1126\/science.1068696","article-title":"Evolutionary rate in the protein interaction network","volume":"296","author":"Fraser","year":"2002","journal-title":"Science"},{"key":"2023020116163790600_btu652-B17","first-page":"174","article-title":"Alignmcl: Comparative analysis of protein interaction networks through markov clustering","volume-title":"Proceedings of the 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)","author":"Guzzi","year":"2012"},{"key":"2023020116163790600_btu652-B18","doi-asserted-by":"crossref","first-page":"C47","DOI":"10.1038\/35011540","article-title":"From molecular to modular cell biology","volume":"402","author":"Hartwell","year":"1999","journal-title":"Nature"},{"key":"2023020116163790600_btu652-B19","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":"2014","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B20","doi-asserted-by":"crossref","first-page":"S6","DOI":"10.1186\/1752-0509-7-S2-S6","article-title":"Corbi: a new r package for biological network alignment and querying","volume":"7","author":"Huang","year":"2013","journal-title":"BMC Syst. Biol."},{"key":"2023020116163790600_btu652-B21","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":"2023020116163790600_btu652-B22","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":"2023020116163790600_btu652-B23","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":"2023020116163790600_btu652-B24","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 Res."},{"key":"2023020116163790600_btu652-B25","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":"2023020116163790600_btu652-B26","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","article-title":"Pairwise local alignment of protein interaction networks guided by models of evolution","volume":"13","author":"Koyut\u00fcrk","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023020116163790600_btu652-B27","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":"2023020116163790600_btu652-B28","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1093\/bioinformatics\/btm156","article-title":"Alignment of molecular networks by integer quadratic programming","volume":"23","author":"Li","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B29","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":"2023020116163790600_btu652-B30","doi-asserted-by":"crossref","first-page":"bar009","DOI":"10.1093\/database\/bar009","article-title":"Uniprot knowledgebase: a hub of integrated protein data","volume":"2011","author":"Magrane","year":"2011","journal-title":"Database"},{"key":"2023020116163790600_btu652-B31","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":"J. Chem. Phys."},{"key":"2023020116163790600_btu652-B32","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4137\/CIN.S4744","article-title":"Optimal network alignment with graphlet degree vectors","volume":"9","author":"Milenkovi\u0107","year":"2010","journal-title":"Cancer Inform."},{"key":"2023020116163790600_btu652-B33","first-page":"23:23","article-title":"Global network alignment in the context of aging","volume-title":"Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics","author":"Milenkovi\u0107","year":"2013"},{"key":"2023020116163790600_btu652-B34","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1093\/bioinformatics\/btt202","article-title":"Netal: a new graph-based method for global alignment of proteinprotein interaction networks","volume":"29","author":"Neyshabur","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B35","doi-asserted-by":"crossref","first-page":"W157","DOI":"10.1093\/nar\/gks446","article-title":"Netalignera network alignment server to compare complexes, pathways and whole interactomes","volume":"40","author":"Pache","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023020116163790600_btu652-B36","doi-asserted-by":"crossref","first-page":"i237","DOI":"10.1093\/bioinformatics\/btt224","article-title":"Predicting protein interactions via parsimonious network history inference","volume":"29","author":"Patro","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B37","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/1748-7188-7-25","article-title":"Parsimonious reconstruction of network evolution","volume":"7","author":"Patro","year":"2012","journal-title":"Algorithms Mol. Biol."},{"key":"2023020116163790600_btu652-B38","doi-asserted-by":"crossref","first-page":"4285","DOI":"10.1073\/pnas.96.8.4285","article-title":"Assigning protein functions by comparative genome analysis: protein phylogenetic profiles","volume":"96","author":"Pellegrini","year":"1999","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020116163790600_btu652-B39","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1093\/bioinformatics\/bts119","article-title":"Pinalog: a novel approach to align protein interaction networks implications for complex detection and function prediction","volume":"28","author":"Phan","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B40","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1126\/science.1162609","article-title":"Conservation and rewiring of functional modules revealed by an epistasis map in fission yeast","volume":"322","author":"Roguev","year":"2008","journal-title":"Science"},{"key":"2023020116163790600_btu652-B41","doi-asserted-by":"crossref","first-page":"D497","DOI":"10.1093\/nar\/gkp914","article-title":"Corum: the comprehensive resource of mammalian protein complexes-2009","volume":"38","author":"Ruepp","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023020116163790600_btu652-B42","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":"2023020116163790600_btu652-B43","doi-asserted-by":"crossref","first-page":"2931","DOI":"10.1093\/bioinformatics\/btu409","article-title":"Magna: Maximizing accuracy in global network alignment","volume":"30","author":"Saraph","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020116163790600_btu652-B44","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":"2023020116163790600_btu652-B45","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":"2023020116163790600_btu652-B46","doi-asserted-by":"crossref","first-page":"16","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, RECOMB\u201907","author":"Singh","year":"2007"},{"key":"2023020116163790600_btu652-B47","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":"2023020116163790600_btu652-B48","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modeling of protein interaction networks","volume":"1","author":"Vazquez","year":"2003","journal-title":"ComPlexUs"},{"key":"2023020116163790600_btu652-B49","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1098\/rspb.2002.2269","article-title":"How the global structure of protein interaction networks evolves","volume":"270","author":"Wagner","year":"2003","journal-title":"Proc. R. Soc. Lond. Ser. B Biol. Sci."},{"key":"2023020116163790600_btu652-B50","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023020116163790600_btu652-B51","first-page":"245","article-title":"Boosting the performance of inference algorithms for transcriptional regulatory networks using a phylogenetic approach","volume-title":"Algorithms in Bioinformatics, volume 5251 of Lecture Notes in Computer Science","author":"Zhang","year":"2008"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/3\/363\/49012607\/bioinformatics_31_3_363.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/3\/363\/49012607\/bioinformatics_31_3_363.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:29:00Z","timestamp":1675297740000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/3\/363\/2365751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,4]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu652","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,2,1]]},"published":{"date-parts":[[2014,10,4]]}}}