{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T18:26:06Z","timestamp":1781634366421,"version":"3.54.5"},"reference-count":49,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1576,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.<\/jats:p>\n               <jats:p>Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods.<\/jats:p>\n               <jats:p>Availability: Our programs can be freely downloaded from http:\/\/compbio.mit.edu\/ranger-dtl\/.<\/jats:p>\n               <jats:p>Contact: \u00a0mukul@csail.mit.edu; manoli@mit.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts225","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T14:09:18Z","timestamp":1339423758000},"page":"i283-i291","source":"Crossref","is-referenced-by-count":192,"title":["Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss"],"prefix":"10.1093","volume":"28","author":[{"given":"Mukul S.","family":"Bansal","sequence":"first","affiliation":[{"name":"1 Computer Science and Artificial Intelligence Laboratory, 2Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA and 3Broad Institute of MIT and Harvard, Cambridge, MA 02142, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric J.","family":"Alm","sequence":"additional","affiliation":[{"name":"1 Computer Science and Artificial Intelligence Laboratory, 2Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA and 3Broad Institute of MIT and Harvard, Cambridge, MA 02142, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manolis","family":"Kellis","sequence":"additional","affiliation":[{"name":"1 Computer Science and Artificial Intelligence Laboratory, 2Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA and 3Broad Institute of MIT and Harvard, Cambridge, MA 02142, USA"},{"name":"1 Computer Science and Artificial Intelligence Laboratory, 2Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA and 3Broad Institute of MIT and Harvard, Cambridge, MA 02142, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2012,6,9]]},"reference":[{"key":"2023012512390309600_B1","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1038\/nrmicro2593","article-title":"Biased gene transfer in microbial evolution","volume":"9","author":"Andam","year":"2011","journal-title":"Nat. Rev. Microbiol."},{"key":"2023012512390309600_B2","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/1502793.1502796","article-title":"The gene evolution model and computing its associated probabilities","volume":"56","author":"Arvestad","year":"2009","journal-title":"J. ACM"},{"key":"2023012512390309600_B3","first-page":"238","article-title":"Heuristics for the gene-duplication problem: a \u0398(n) speed-up for the local search","volume-title":"RECOMB","author":"Bansal","year":"2007"},{"key":"2023012512390309600_B4","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","article-title":"Lowest common ancestors in trees and directed acyclic graphs","volume":"57","author":"Bender","year":"2005","journal-title":"J. Algor."},{"key":"2023012512390309600_B5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1093\/sysbio\/syp103","article-title":"Inferring and validating horizontal gene transfer events using bipartition dissimilarity","volume":"59","author":"Boc","year":"2010","journal-title":"Syst. Biol."},{"key":"2023012512390309600_B6","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2005.05.016","article-title":"Reconciling a gene tree to a species tree under the duplication cost model","volume":"347","author":"Bonizzoni","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"2023012512390309600_B7","first-page":"290","article-title":"Path minima queries in dynamic weighted trees","volume-title":"WADS.","author":"Brodal","year":"2011"},{"key":"2023012512390309600_B8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1093\/sysbio\/syq072","article-title":"Genome-scale phylogenetics: inferring the plant tree of life from 18,896 gene trees","volume":"60","author":"Burleigh","year":"2011","journal-title":"Syst. Biol."},{"key":"2023012512390309600_B9","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/S0025-5564(97)10012-8","article-title":"Jungles: a new solution to the host\u2013parasite phylogeny reconciliation problem","volume":"149","author":"Charleston","year":"1998","journal-title":"Math. Biosci."},{"key":"2023012512390309600_B10","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jbi.2005.08.006","article-title":"Traversing the tangle: algorithms and applications for cophylogenetic studies","volume":"39","author":"Charleston","year":"2006","journal-title":"J. Biomed. Inform."},{"key":"2023012512390309600_B11","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1089\/cmb.2008.0054","article-title":"Gene family evolution by duplication, speciation, and loss","volume":"15","author":"Chauve","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B12","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1089\/106652700750050871","article-title":"Notung: a program for dating gene duplications and optimizing gene family trees","volume":"7","author":"Chen","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B13","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1186\/1748-7188-5-16","article-title":"Jane: a new tool for the cophylogeny reconstruction problem","volume":"5","author":"Conow","year":"2010","journal-title":"Algorithm. Mol. Biol."},{"key":"2023012512390309600_B14","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009","edition":"3rd"},{"key":"2023012512390309600_B15","first-page":"206","article-title":"A probabilistic model for gene content evolution with duplication, loss, and horizontal transfer","volume":"3909","author":"Cs\u00fcr\u00f6s","year":"2006","journal-title":"RECOMB"},{"key":"2023012512390309600_B16","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1038\/nature09649","article-title":"Rapid evolutionary innovation during an archaean genetic expansion","volume":"469","author":"David","year":"2011","journal-title":"Nature"},{"key":"2023012512390309600_B17","first-page":"93","article-title":"An efficient algorithm for gene\/species trees parsimonious reconciliation with losses, duplications and transfers","volume-title":"RECOMB-CG","author":"Doyon","year":"2010"},{"key":"2023012512390309600_B18","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1089\/cmb.2006.13.320","article-title":"A hybrid micro-macroevolutionary approach to gene tree reconstruction","volume":"13","author":"Durand","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0166-218X(98)00068-7","article-title":"On the equivalence of two tree mapping measures","volume":"88","author":"Eulenstein","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"2023012512390309600_B20","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/2412519","article-title":"Fitting the gene lineage into its species lineage. A parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Zool."},{"key":"2023012512390309600_B21","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1134\/S0026893309050197","article-title":"Reconstructing genes evolution along a species tree","volume":"43","author":"Gorbunov","year":"2009","journal-title":"Mol. Biol."},{"key":"2023012512390309600_B22","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.tcs.2006.05.019","article-title":"Dls-trees: a model of evolutionary scenarios","volume":"359","author":"G\u00f3recki","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2023012512390309600_B23","first-page":"149","article-title":"Efficient algorithms for lateral gene transfer problems","volume-title":"Proceedings of the fifth Annual International Conference on Research in Computational Molecular Biology (RECOMB)","author":"Hallett","year":"2001"},{"key":"2023012512390309600_B24","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1186\/1471-2148-10-42","article-title":"Sprit: identifying horizontal gene transfer in rooted phylogenetic trees","volume":"10","author":"Hill","year":"2010","journal-title":"BMC Evol. Biol."},{"key":"2023012512390309600_B25","first-page":"352","article-title":"A Bayesian framework for the analysis of cospeciation","volume":"54","author":"Huelsenbeck","year":"2000","journal-title":"Evolution"},{"key":"2023012512390309600_B26","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCBB.2008.119","article-title":"Parsimony score of phylogenetic networks: hardness results and a linear-time heuristic","volume":"6","author":"Jin","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinforma."},{"key":"2023012512390309600_B27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1146\/annurev.genet.39.073003.114725","article-title":"Orthologs, paralogs, and evolutionary genomics","volume":"39","author":"Koonin","year":"2005","journal-title":"Annu. Rev. Genet."},{"key":"2023012512390309600_B28","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1089\/cmb.2008.0084","article-title":"On the computational complexity of the reticulate cophylogeny reconstruction problem","volume":"16","author":"Libeskind-Hadas","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B29","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1089\/cmb.2008.0069","article-title":"Dupcar: reconstructing contiguous ancestral regions with duplications","volume":"15","author":"Ma","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B30","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.thbio.2005.01.003","article-title":"Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information","volume":"123","author":"Merkle","year":"2005","journal-title":"Theor. Biosci."},{"issue":"Suppl. 1","key":"2023012512390309600_B31","doi-asserted-by":"crossref","first-page":"S60","DOI":"10.1186\/1471-2105-11-S1-S60","article-title":"A parameter-adaptive dynamic programming approach for inferring cophylogenies","volume":"11","author":"Merkle","year":"2010","journal-title":"BMC Bioinform."},{"issue":"Suppl. 1","key":"2023012512390309600_B32","doi-asserted-by":"crossref","first-page":"D204","DOI":"10.1093\/nar\/gkp1019","article-title":"Panther version 7: improved phylogenetic trees, orthologs and collaboration with the gene ontology consortium","volume":"38","author":"Mi","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012512390309600_B33","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1995.2.493","article-title":"A biologically consistent model for comparing molecular phylogenies","volume":"2","author":"Mirkin","year":"1995","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B34","first-page":"337","article-title":"Reconstructing reticulate evolution in species: theory and practice","volume-title":"Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004","author":"Nakhleh","year":"2004"},{"key":"2023012512390309600_B35","first-page":"84","article-title":"{RIATA-HGT}: a fast and accurate heuristic for reconstructing horizontal gene transfer","volume-title":"COCOON","author":"Nakhleh","year":"2005"},{"key":"2023012512390309600_B36","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1089\/cmb.2009.0240","article-title":"The cophylogeny reconstruction problem is np-complete","volume":"18","author":"Ovadia","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012512390309600_B37","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":"2023012512390309600_B38","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1093\/molbev\/msq189","article-title":"A Bayesian approach for fast and accurate gene tree reconstruction","volume":"28","author":"Rasmussen","year":"2011","journal-title":"Mol. Biol. Evol."},{"key":"2023012512390309600_B39","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1111\/j.1096-0031.1995.tb00005.x","article-title":"Reconstructing the history of host\u2013parasite associations using generalised parsimony","volume":"11","author":"Ronquist","year":"1995","journal-title":"Cladistics"},{"key":"2023012512390309600_B40","first-page":"22","article-title":"Parsimony analysis of coevolving species associations","volume-title":"Tangled Trees: Phylogeny, Cospeciation and Coevolution","author":"Ronquist","year":"2003"},{"key":"2023012512390309600_B41","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1111\/j.1366-9516.2006.00210.x","article-title":"Molecular dating of phylogenetic trees: a brief review of current methods that estimate divergence times","volume":"12","author":"Rutschmann","year":"2006","journal-title":"Divers. Distrib."},{"key":"2023012512390309600_B42","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1093\/sysbio\/syp046","article-title":"Probabilistic orthology analysis","volume":"58","author":"Sennblad","year":"2009","journal-title":"Syst. Biol."},{"key":"2023012512390309600_B43","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1093\/bioinformatics\/18.1.92","article-title":"Automated ortholog inference from phylogenetic trees and calculation of orthology reliability","volume":"18","author":"Storm","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012512390309600_B44","article-title":"Using trees to capture reticulate evolution: lateral gene transfers and cancer progression","volume-title":"PhD Thesis","author":"Tofigh","year":"2009"},{"key":"2023012512390309600_B45","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1109\/TCBB.2010.14","article-title":"Simultaneous identification of duplications and lateral gene transfers","volume":"8","author":"Tofigh","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012512390309600_B46","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1186\/1471-2105-8-83","article-title":"Orthology prediction at scalable resolution by phylogenetic tree analysis","volume":"8","author":"van der Heijden","year":"2007","journal-title":"BMC Bioinform."},{"key":"2023012512390309600_B47","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1101\/gr.073585.107","article-title":"Ensemblcompara genetrees: complete, duplication-aware phylogenetic trees in vertebrates","volume":"19","author":"Vilella","year":"2009","journal-title":"Genome Res."},{"key":"2023012512390309600_B48","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/359460.359478","article-title":"A data structure for manipulating priority queues","volume":"21","author":"Vuillemin","year":"1978","journal-title":"{Commun. ACM"},{"key":"2023012512390309600_B49","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1038\/nature06107","article-title":"Natural history and evolutionary principles of gene duplication in fungi","volume":"449","author":"Wapinski","year":"2007","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i283\/48880395\/bioinformatics_28_12_i283.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i283\/48880395\/bioinformatics_28_12_i283.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T16:41:27Z","timestamp":1674664887000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/12\/i283\/269262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,9]]},"references-count":49,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts225","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,6,15]]},"published":{"date-parts":[[2012,6,9]]}}}