{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:03:59Z","timestamp":1773277439426,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T00:00:00Z","timestamp":1475452800000},"content-version":"vor","delay-in-days":845,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem.<\/jats:p>\n               <jats:p>Results: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies.<\/jats:p>\n               <jats:p>Availability and implementation: Our Python tools are freely available at www.cs.hmc.edu\/\u223chadas\/xscape.<\/jats:p>\n               <jats:p>Contact: \u00a0mukul@engr.uconn.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu289","type":"journal-article","created":{"date-parts":[[2014,6,16]],"date-time":"2014-06-16T21:55:09Z","timestamp":1402955709000},"page":"i87-i95","source":"Crossref","is-referenced-by-count":63,"title":["Pareto-optimal phylogenetic tree reconciliation"],"prefix":"10.1093","volume":"30","author":[{"given":"Ran","family":"Libeskind-Hadas","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, 2Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, 3Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and 4Broad Institute, Cambridge, MA 02142, USA"}]},{"given":"Yi-Chieh","family":"Wu","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, 2Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, 3Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and 4Broad Institute, Cambridge, MA 02142, USA"}]},{"given":"Mukul S.","family":"Bansal","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, 2Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, 3Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and 4Broad Institute, Cambridge, MA 02142, USA"}]},{"given":"Manolis","family":"Kellis","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, 2Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, 3Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and 4Broad Institute, Cambridge, MA 02142, USA"},{"name":"1 Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, 2Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, 3Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and 4Broad Institute, Cambridge, MA 02142, USA"}]}],"member":"286","published-online":{"date-parts":[[2014,6,11]]},"reference":[{"key":"2023012711105062900_btu289-B1","first-page":"279","article-title":"Towards identifying lateral gene transfer events","volume":"8","author":"Addario-Berry","year":"2003","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012711105062900_btu289-B2","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1093\/bioinformatics\/bts225","article-title":"Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss","volume":"28","author":"Bansal","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012711105062900_btu289-B3","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1089\/cmb.2013.0073","article-title":"Reconciliation revisited: Handling multiple optima when reconciling with duplication, transfer, and loss","volume":"20","author":"Bansal","year":"2013","journal-title":"J. Comput. Biol."},{"key":"2023012711105062900_btu289-B4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"Berg","year":"2008","edition":"3rd edn"},{"key":"2023012711105062900_btu289-B5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/S0025-5564(97)10012-8","article-title":"Jungles: a new solution to the host-parasite phylogeny reconciliation problem","volume":"149","author":"Charleston","year":"1998","journal-title":"Math. Biosci."},{"key":"2023012711105062900_btu289-B6","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1109\/TCBB.2012.79","article-title":"Simultaneous identification of duplications, losses, and lateral gene transfers","volume":"9","author":"Chen","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012711105062900_btu289-B7","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":"2023012711105062900_btu289-B8","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":"2023012711105062900_btu289-B9","first-page":"93","article-title":"An efficient algorithm for gene\/species trees parsimonious reconciliation with losses, duplications and transfers","volume-title":"RECOMB-CG, volume 6398 of Lecture Notes in Computer Science","author":"Doyon","year":"2010"},{"key":"2023012711105062900_btu289-B10","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1038\/nature09113","article-title":"Ecological interactions are evolutionarily conserved across the entire tree of life","volume":"465","author":"G\u00f3mez","year":"2010","journal-title":"Nature"},{"key":"2023012711105062900_btu289-B11","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":"2023012711105062900_btu289-B12","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1038\/332258a0","article-title":"Phylogenetic trees support the coevolution of parasites and their hosts","volume":"332","author":"Hafner","year":"1988","journal-title":"Nature"},{"key":"2023012711105062900_btu289-B13","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/974614.974660","article-title":"Simultaneous identification of duplications and lateral transfers","volume-title":"RECOMB","author":"Hallett","year":"2004"},{"key":"2023012711105062900_btu289-B14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1093\/molbev\/msg232","article-title":"A cophylogenetic perspective of RNA-virus evolution","volume":"21","author":"Jackson","year":"2004","journal-title":"Mol. Biol. Evol."},{"key":"2023012711105062900_btu289-B15","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":"2023012711105062900_btu289-B16","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":"2023012711105062900_btu289-B17","volume-title":"Evolutionary Biogeography: An Integrative Approach with Case Studies","author":"Morrone","year":"2009"},{"key":"2023012711105062900_btu289-B18","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":"2023012711105062900_btu289-B19","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":"2023012711105062900_btu289-B20","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":"2023012711105062900_btu289-B21","doi-asserted-by":"crossref","first-page":"1250025","DOI":"10.1142\/S0219720012500254","article-title":"Representing a set of reconciliations in a compact way","volume":"11","author":"Scornavacca","year":"2013","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023012711105062900_btu289-B22","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1080\/10635150490265021","article-title":"Clade-limited colonization in brood parasitic finches (vidua spp.)","volume":"53","author":"Sorenson","year":"2004","journal-title":"Syst. Biol."},{"key":"2023012711105062900_btu289-B23","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1093\/bioinformatics\/bts386","article-title":"Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees","volume":"28","author":"Stolzer","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012711105062900_btu289-B24","doi-asserted-by":"crossref","first-page":"17513","DOI":"10.1073\/pnas.1202997109","article-title":"Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative timing of speciations","volume":"109","author":"Szollosi","year":"2012","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711105062900_btu289-B25","article-title":"Using trees to capture reticulate evolution: lateral gene transfers and cancer progression","author":"Tofigh","year":"2009"},{"key":"2023012711105062900_btu289-B26","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."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/12\/i87\/48927334\/bioinformatics_30_12_i87.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/12\/i87\/48927334\/bioinformatics_30_12_i87.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:50:58Z","timestamp":1674820258000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/12\/i87\/390654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,11]]},"references-count":26,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu289","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,6,15]]},"published":{"date-parts":[[2014,6,11]]}}}