{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T20:29:58Z","timestamp":1776457798713,"version":"3.51.2"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1490,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Gene duplication (D), transfer (T), loss (L) and incomplete lineage sorting (I) are crucial to the evolution of gene families and the emergence of novel functions. The history of these events can be inferred via comparison of gene and species trees, a process called reconciliation, yet current reconciliation algorithms model only a subset of these evolutionary processes.<\/jats:p>\n               <jats:p>Results: We present an algorithm to reconcile a binary gene tree with a nonbinary species tree under a DTLI parsimony criterion. This is the first reconciliation algorithm to capture all four evolutionary processes driving tree incongruence and the first to reconcile non-binary species trees with a transfer model. Our algorithm infers all optimal solutions and reports complete, temporally feasible event histories, giving the gene and species lineages in which each event occurred. It is fixed-parameter tractable, with polytime complexity when the maximum species outdegree is fixed. Application of our algorithms to prokaryotic and eukaryotic data show that use of an incomplete event model has substantial impact on the events inferred and resulting biological conclusions.<\/jats:p>\n               <jats:p>Availability: Our algorithms have been implemented in Notung, a freely available phylogenetic reconciliation software package, available at http:\/\/www.cs.cmu.edu\/~durand\/Notung.<\/jats:p>\n               <jats:p>Contact: \u00a0mstolzer@andrew.cmu.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts386","type":"journal-article","created":{"date-parts":[[2012,9,7]],"date-time":"2012-09-07T20:35:22Z","timestamp":1347050122000},"page":"i409-i415","source":"Crossref","is-referenced-by-count":314,"title":["Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees"],"prefix":"10.1093","volume":"28","author":[{"given":"Maureen","family":"Stolzer","sequence":"first","affiliation":[{"name":"1 Department of Biological Sciences"}]},{"given":"Han","family":"Lai","sequence":"additional","affiliation":[{"name":"1 Department of Biological Sciences"}]},{"given":"Minli","family":"Xu","sequence":"additional","affiliation":[{"name":"2 Lane Center for Computational Biology"}]},{"given":"Deepa","family":"Sathaye","sequence":"additional","affiliation":[{"name":"3 Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA"}]},{"given":"Benjamin","family":"Vernot","sequence":"additional","affiliation":[{"name":"4 Department of Genome Sciences, University of Washington, Seattle, WA 98195, USA"}]},{"given":"Dannie","family":"Durand","sequence":"additional","affiliation":[{"name":"1 Department of Biological Sciences"},{"name":"3 Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA"}]}],"member":"286","published-online":{"date-parts":[[2012,9,3]]},"reference":[{"key":"2023012513044557000_B1","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/978-1-60327-853-9_27","article-title":"Horizontal gene transfer between microbial eukaryotes","volume":"532","author":"Andersson","year":"2009","journal-title":"Methods Mol. Biol."},{"key":"2023012513044557000_B2","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1089\/cmb.2011.0066","article-title":"Detecting highways of horizontal gene transfer","volume":"18","author":"Bansal","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012513044557000_B3","doi-asserted-by":"crossref","first-page":"14332","DOI":"10.1073\/pnas.0504068102","article-title":"Highways of gene sharing in prokaryotes","volume":"102","author":"Beiko","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012513044557000_B4","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/s00239-005-0096-1","article-title":"Optimal gene trees from sequences and species trees using a soft interpretation of parsimony","volume":"63","author":"Berglund","year":"2006","journal-title":"J. Mol. Evol."},{"key":"2023012513044557000_B5","volume-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"2023012513044557000_B6","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":"2023012513044557000_B7","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.tree.2009.01.009","article-title":"Gene tree discordance, phylogenetic inference and the multispecies coalescent","volume":"24","author":"Degnan","year":"2009","journal-title":"Trends Ecol. Evol."},{"key":"2023012513044557000_B8","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1038\/nrg1603","article-title":"Phylogenomics and the reconstruction of the tree of life","volume":"6","author":"Delsuc","year":"2005","journal-title":"Nat. Rev. Genet."},{"key":"2023012513044557000_B9","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1093\/bib\/bbr045","article-title":"Models, algorithms and programs for phylogeny reconciliation","volume":"12","author":"Doyon","year":"2011","journal-title":"Brief Bioinform."},{"key":"2023012513044557000_B10","doi-asserted-by":"crossref","first-page":"2266","DOI":"10.1093\/molbev\/msm156","article-title":"Mapping human genetic ancestry","volume":"24","author":"Ebersberger","year":"2007","journal-title":"Mol. Biol. Evol."},{"key":"2023012513044557000_B11","first-page":"1","article-title":"2009?","volume":"63","author":"Edwards","year":"2009","journal-title":"Is a new and general theory of molecular systematics emerging"},{"key":"2023012513044557000_B12","first-page":"347","article-title":"Simultaneous identification of duplications and lateral transfers","volume-title":"RECOMB 2004: Proceedings of the Eigth International Conference on Research in Computational Biology","author":"Hallett","year":"2004"},{"key":"2023012513044557000_B13","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/gbe\/evq077","article-title":"A survey of combinatorial methods for phylogenetic networks","volume":"3","author":"Huson","year":"2011","journal-title":"Genome Biol. Evol."},{"key":"2023012513044557000_B14","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1137\/S0097539798343362","article-title":"From gene trees to species trees","volume":"30","author":"Ma","year":"2000","journal-title":"SIAM J. Comput."},{"key":"2023012513044557000_B15","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","article-title":"Gene trees in species trees","volume":"46","author":"Maddison","year":"1997","journal-title":"Syst. Biol."},{"key":"2023012513044557000_B16","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/10635150500354928","article-title":"Inferring phylogeny despite incomplete lineage sorting","volume":"55","author":"Maddison","year":"2006","journal-title":"Syst. Biol."},{"key":"2023012513044557000_B17","article-title":"Mesquite: A modular system for evolutionary analysis, version 2.75","author":"Maddison","year":"2011"},{"key":"2023012513044557000_B18","doi-asserted-by":"crossref","first-page":"R16","DOI":"10.1186\/gb-2010-11-2-r16","article-title":"2x genomes\u2013depth does matter","volume":"11","author":"Milinkovitch","year":"2010","journal-title":"Genome Biol."},{"key":"2023012513044557000_B19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-0-387-09760-2_7","article-title":"Evolutionary phylogenetic networks: models and issues","volume-title":"The Problem Solving Handbook for Computational Biology and Bioinformatics","author":"Nakhleh","year":"2010"},{"key":"2023012513044557000_B20","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1201\/9781420010626.ch17","article-title":"Gene trees, species trees, and species networks","volume-title":"Meta-analysis and Combining Information in Genetics and Genomics","author":"Nakhleh","year":"2009"},{"key":"2023012513044557000_B21","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","article-title":"Gene Tree: comparing gene and species phylogenies using reconciled trees","volume":"14","author":"Page","year":"1998","journal-title":"Bioinformatics"},{"key":"2023012513044557000_B22","doi-asserted-by":"crossref","first-page":"e173","DOI":"10.1371\/journal.pgen.0020173","article-title":"Widespread discordance of gene trees with species tree in Drosophila: evidence for incomplete lineage sorting","volume":"2","author":"Pollard","year":"2006","journal-title":"PLoS Genet."},{"key":"2023012513044557000_B23","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1101\/gr.123901.111","article-title":"Unified modeling of gene duplication, loss, and coalescence using a locus tree","volume":"4","author":"Rasmussen","year":"2012","journal-title":"Genome Res."},{"key":"2023012513044557000_B24","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1038\/nature02053","article-title":"Genome-scale approaches to resolving incongruence in molecular phylogenies","volume":"425","author":"Rokas","year":"2003","journal-title":"Nature"},{"key":"2023012513044557000_B25","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1186\/1471-2148-11-45","article-title":"The origin of multicellularity in cyanobacteria","volume":"11","author":"Schirrmeister","year":"2011","journal-title":"BMC Evol. Biol."},{"key":"2023012513044557000_B26","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1186\/1745-6150-4-46","article-title":"Evolution by leaps: gene duplication in bacteria","volume":"4","author":"Serres","year":"2009","journal-title":"Biol. Direct."},{"key":"2023012513044557000_B27","doi-asserted-by":"crossref","first-page":"e1000501","DOI":"10.1371\/journal.pcbi.1000501","article-title":"Species tree inference by minimizing deep coalescences","volume":"5","author":"Than","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012513044557000_B28","first-page":"517","article-title":"Simultaneous identification of duplications and lateral gene transfers","volume":"8","author":"Tofigh","year":"2011","journal-title":"TCBB"},{"key":"2023012513044557000_B29","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1089\/cmb.2008.0092","article-title":"Reconciliation with non-binary species trees","volume":"15","author":"Vernot","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012513044557000_B30","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1093\/sysbio\/syq084","article-title":"Coalescent histories on phylogenetic networks and detection of hybridization despite incomplete lineage sorting","volume":"60","author":"Yu","year":"2011","journal-title":"Syst. Biol."},{"key":"2023012513044557000_B31","doi-asserted-by":"crossref","first-page":"1685","DOI":"10.1109\/TCBB.2011.83","article-title":"From gene trees to species trees ii: Species tree inference by minimizing deep coalescence events","volume":"6","author":"Zhang","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012513044557000_B32","doi-asserted-by":"crossref","first-page":"R242","DOI":"10.1016\/j.cub.2011.01.045","article-title":"Lateral gene transfer","volume":"21","author":"Zhaxybayeva","year":"2011","journal-title":"Curr. Biol."},{"key":"2023012513044557000_B33","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1093\/gbe\/evp032","article-title":"Intertwined evolutionary histories of marine Synechococcus and Prochlorococcus marinus","volume":"1","author":"Zhaxybayeva","year":"2009","journal-title":"Genome Biol. Evol."},{"key":"2023012513044557000_B34","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1093\/bioinformatics\/17.9.821","article-title":"A simple algorithm to infer gene duplication and speciation events on a gene tree","volume":"17","author":"Zmasek","year":"2001","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i409\/48884879\/bioinformatics_28_18_i409.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i409\/48884879\/bioinformatics_28_18_i409.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T18:56:49Z","timestamp":1674673009000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/18\/i409\/246367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,3]]},"references-count":34,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2012,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts386","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,9,15]]},"published":{"date-parts":[[2012,9,3]]}}}