{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T19:55:41Z","timestamp":1719258941724},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,5,1]]},"abstract":"Abstract<\/jats:title>\n Motivation: Determining the interaction partners among protein\/domain families poses hard computational problems, in particular in the presence of paralogous proteins. Available approaches aim to identify interaction partners among protein\/domain families through maximizing the similarity between trimmed versions of their phylogenetic trees. Since maximization of any natural similarity score is computationally difficult, many approaches employ heuristics to evaluate the distance matrices corresponding to the tree topologies in question. In this article, we devise an efficient deterministic algorithm which directly maximizes the similarity between two leaf labeled trees with edge lengths, obtaining a score-optimal alignment of the two trees in question.<\/jats:p>\n Results: Our algorithm is significantly faster than those methods based on distance matrix comparison: 1 min on a single processor versus 730 h on a supercomputer. Furthermore, we outperform the current state-of-the-art exhaustive search approach in terms of precision, while incurring acceptable losses in recall.<\/jats:p>\n Availability: A C implementation of the method demonstrated in this article is available at http:\/\/compbio.cs.sfu.ca\/mirrort.htm<\/jats:p>\n Contact: \u00a0imanh@sfu.ca; cenk@sfu.ca; as@cwi.nl<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts109","type":"journal-article","created":{"date-parts":[[2012,3,8]],"date-time":"2012-03-08T01:14:56Z","timestamp":1331169296000},"page":"1202-1208","source":"Crossref","is-referenced-by-count":5,"title":["Mirroring co-evolving trees in the light of their topologies"],"prefix":"10.1093","volume":"28","author":[{"given":"Iman","family":"Hajirasouliha","sequence":"first","affiliation":[{"name":"1 School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, 2Centrum Wiskunde & Informatica (CWI), Science Park 123 1098 XG, Amsterdam, The Netherlands and 3Structural Biology and Biocomputing Programme (CNIO) Spanish National Cancer Research Centre, 28029 Madrid, Spain"}]},{"given":"Alexander","family":"Sch\u00f6nhuth","sequence":"additional","affiliation":[{"name":"1 School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, 2Centrum Wiskunde & Informatica (CWI), Science Park 123 1098 XG, Amsterdam, The Netherlands and 3Structural Biology and Biocomputing Programme (CNIO) Spanish National Cancer Research Centre, 28029 Madrid, Spain"}]},{"given":"David","family":"de Juan","sequence":"additional","affiliation":[{"name":"1 School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, 2Centrum Wiskunde & Informatica (CWI), Science Park 123 1098 XG, Amsterdam, The Netherlands and 3Structural Biology and Biocomputing Programme (CNIO) Spanish National Cancer Research Centre, 28029 Madrid, Spain"}]},{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[{"name":"1 School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, 2Centrum Wiskunde & Informatica (CWI), Science Park 123 1098 XG, Amsterdam, The Netherlands and 3Structural Biology and Biocomputing Programme (CNIO) Spanish National Cancer Research Centre, 28029 Madrid, Spain"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"1 School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, 2Centrum Wiskunde & Informatica (CWI), Science Park 123 1098 XG, Amsterdam, The Netherlands and 3Structural Biology and Biocomputing Programme (CNIO) Spanish National Cancer Research Centre, 28029 Madrid, Spain"}]}],"member":"286","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"key":"2023012512235464700_B1","volume-title":"Tree edit distance, alignment and inclusion.","author":"Bille","year":"2003"},{"key":"2023012512235464700_B2","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1093\/bioinformatics\/btg278","article-title":"Inferring protein interactions from phylogenetic distance matrices","volume":"19","author":"Gertz","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012512235464700_B3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/1471-2105-9-35","article-title":"Enhancing the prediction of protein pairings between interacting families using orthology information","volume":"9","author":"Izarzugaza","year":"2008","journal-title":"BMC Bioinformatics"},{"issue":"Suppl. 1","key":"2023012512235464700_B4","doi-asserted-by":"crossref","first-page":"i241","DOI":"10.1093\/bioinformatics\/bti1009","article-title":"Predicting protein-protein interaction by searching evolutionary tree automorphism space","volume":"21","author":"Jothi","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012512235464700_B5","doi-asserted-by":"crossref","first-page":"2567","DOI":"10.1093\/molbev\/msq144","article-title":"An integrated view of molecular co-evolution in protein-protein interactions","volume":"27","author":"Lovell","year":"2010","journal-title":"Mol. Biol. Evol."},{"key":"2023012512235464700_B6","first-page":"58","article-title":"Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas","volume":"43","author":"Page","year":"1994","journal-title":"Syst. Biol."},{"key":"2023012512235464700_B7","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1093\/protein\/14.9.609","article-title":"Similarity of phylogenetic trees as indicator of protein-protein interaction","volume":"14","author":"Pazos","year":"2001","journal-title":"Protein Eng."},{"key":"2023012512235464700_B8","doi-asserted-by":"crossref","first-page":"2648","DOI":"10.1038\/emboj.2008.189","article-title":"Protein co-evolution, co-adaptation and interactions","volume":"27","author":"Pazos","year":"2008","journal-title":"EMBO J."},{"key":"2023012512235464700_B9","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":"2023012512235464700_B10","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1016\/j.jda.2007.07.001","article-title":"Approximate labelled subtree homeomorphism","volume":"6","author":"Pinter","year":"2008","journal-title":"J. Discr. Algor."},{"key":"2023012512235464700_B11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0022-2836(03)00114-1","article-title":"Exploiting the co-evolution of interacting proteins to discover interaction specificity","volume":"327","author":"Ramani","year":"2003","journal-title":"J. Mol. Biol."},{"key":"2023012512235464700_B12","doi-asserted-by":"crossref","first-page":"2937","DOI":"10.1016\/j.patcog.2010.03.015","article-title":"Homeomorphic alignment of weighted trees","volume":"43","author":"Raynal","year":"2010","journal-title":"Pattern Recogn."},{"key":"2023012512235464700_B13","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","article-title":"The tree-to-tree correction problem","volume":"26","author":"Tai","year":"1979","journal-title":"J. ACM"},{"key":"2023012512235464700_B14","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"Clustal w: improving the sensitivity of progressive multiple sequence alignments through sequence weighting, position specific gap penalties and weight matrix choice","volume":"18","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012512235464700_B15","doi-asserted-by":"crossref","first-page":"1861","DOI":"10.1101\/gr.092452.109","article-title":"The human protein coevolution network","volume":"19","author":"Tillier","year":"2009","journal-title":"Genome Res."},{"key":"2023012512235464700_B16","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1002\/prot.20948","article-title":"Codep: maximizing co-evolutionary interdependencies to discover interacting proteins","volume":"63","author":"Tillier","year":"2006","journal-title":"Prot. Struc. Func. Bioinform."},{"key":"2023012512235464700_B17","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1023\/A:1020667228952","article-title":"Tree conciliation: reconstruction of species phylogeny by phylogenetic gene trees","volume":"36","author":"Vyugin","year":"2002","journal-title":"Mol. Biol."},{"key":"2023012512235464700_B18","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/molbev\/msl193","article-title":"Phylogenetic methodology for detecting protein interactions","volume":"24","author":"Waddell","year":"2007","journal-title":"Mol. Biol. Evol."},{"key":"2023012512235464700_B19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","article-title":"Some MAX-SNP-hard results concerning unordered labeled trees","volume":"49","author":"Zhang","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"2023012512235464700_B20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","article-title":"On the editing distance between unordered labeled trees","volume":"42","author":"Zhang","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"2023012512235464700_B21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01975866","article-title":"A constrained edit distance between unordered labeled trees","volume":"15","author":"Zhang","year":"1996","journal-title":"Algorithmica"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/9\/1202\/48880312\/bioinformatics_28_9_1202.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/9\/1202\/48880312\/bioinformatics_28_9_1202.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T15:54:16Z","timestamp":1674662056000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/9\/1202\/311395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,6]]},"references-count":21,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2012,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts109","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,5,1]]},"published":{"date-parts":[[2012,3,6]]}}}