{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:37:39Z","timestamp":1773869859010,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":772,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Large-scale methods for inferring gene trees are error-prone. Correcting gene trees for weakly supported features often results in non-binary trees, i.e. trees with polytomies, thus raising the natural question of refining such polytomies into binary trees. A feature pointing toward potential errors in gene trees are duplications that are not supported by the presence of multiple gene copies.<\/jats:p>\n               <jats:p>Results: We introduce the problem of refining polytomies in a gene tree while minimizing the number of created non-apparent duplications in the resulting tree. We show that this problem can be described as a graph-theoretical optimization problem. We provide a bounded heuristic with guaranteed optimality for well-characterized instances. We apply our algorithm to a set of ray-finned fish gene trees from the Ensembl database to illustrate its ability to correct dubious duplications.<\/jats:p>\n               <jats:p>Availability and implementation: The C++ source code for the algorithms and simulations described in the article are available at http:\/\/www-ens.iro.umontreal.ca\/~lafonman\/software.php.<\/jats:p>\n               <jats:p>Contact: \u00a0lafonman@iro.umontreal.ca or mabrouk@iro.umontreal.ca<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu463","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T11:23:57Z","timestamp":1409052237000},"page":"i519-i526","source":"Crossref","is-referenced-by-count":20,"title":["Polytomy refinement for the correction of dubious duplications in gene trees"],"prefix":"10.1093","volume":"30","author":[{"given":"Manuel","family":"Lafond","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec H3C 3J7, Canada, 2LaBRI, Universit\u00e9 Bordeaux 1, Bordeaux, France, 3Department of Mathematics, Simon Fraser University, Burnaby (BC) V5A 1S6, Canada and 4Universit\u00e1 degli Studi di Bergamo, Bergamo 24129 IT, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec H3C 3J7, Canada, 2LaBRI, Universit\u00e9 Bordeaux 1, Bordeaux, France, 3Department of Mathematics, Simon Fraser University, Burnaby (BC) V5A 1S6, Canada and 4Universit\u00e1 degli Studi di Bergamo, Bergamo 24129 IT, Italy"},{"name":"1 Department of Computer Science, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec H3C 3J7, Canada, 2LaBRI, Universit\u00e9 Bordeaux 1, Bordeaux, France, 3Department of Mathematics, Simon Fraser University, Burnaby (BC) V5A 1S6, Canada and 4Universit\u00e1 degli Studi di Bergamo, Bergamo 24129 IT, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec H3C 3J7, Canada, 2LaBRI, Universit\u00e9 Bordeaux 1, Bordeaux, France, 3Department of Mathematics, Simon Fraser University, Burnaby (BC) V5A 1S6, Canada and 4Universit\u00e1 degli Studi di Bergamo, Bergamo 24129 IT, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec H3C 3J7, Canada, 2LaBRI, Universit\u00e9 Bordeaux 1, Bordeaux, France, 3Department of Mathematics, Simon Fraser University, Burnaby (BC) V5A 1S6, Canada and 4Universit\u00e1 degli Studi di Bergamo, Bergamo 24129 IT, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,8,22]]},"reference":[{"key":"2023012711542292900_btu463-B1","doi-asserted-by":"crossref","first-page":"5714","DOI":"10.1073\/pnas.0806251106","article-title":"Simultaneous bayesian gene tree reconstruction and reconciliation analysis","volume":"106","author":"Akerborg","year":"2009","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711542292900_btu463-B2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1471-2148-6-15","article-title":"Phylogenetic identification of lateral genetic transfer events","volume":"6","author":"Beiko","year":"2006","journal-title":"BMC Evol. Biol."},{"key":"2023012711542292900_btu463-B3","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/s00239-005-0096-1","article-title":"Liberles. Optimal gene trees from sequences and species trees using a soft interpretation of parsimony","volume":"63","author":"Berglund-Sonnhammer","year":"2006","journal-title":"J. Mol. Evol."},{"key":"2023012711542292900_btu463-B4","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1101\/gr.141978.112","article-title":"Genome-scale coestimation of species and gene trees","volume":"23","author":"Boussau","year":"2012","journal-title":"Genome Res."},{"key":"2023012711542292900_btu463-B5","doi-asserted-by":"crossref","DOI":"10.1007\/11809678_26","article-title":"Reconciling gene trees with apparent polytomies","author":"Chang","year":"2006"},{"issue":"Suppl.10","key":"2023012711542292900_btu463-B6","first-page":"S11","article-title":"Efficient error correction algorithms for gene tree reconciliation based on duplication, duplication and loss, and deep coalescence","volume":"13","author":"Chaudhary","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012711542292900_btu463-B7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-02008-7_4","article-title":"New perspectives on gene family evolution: losses in reconciliation and a link with supertrees","author":"Chauve","year":"2009"},{"key":"2023012711542292900_btu463-B8","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1089\/106652700750050871","article-title":"Notung: dating gene duplications using gene family trees","volume":"7","author":"Chen","year":"2000","journal-title":"J. Comp. Biol."},{"key":"2023012711542292900_btu463-B9","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","article-title":"A linear recognition algorithm for cographs","volume":"14","author":"Corneil","year":"1985","journal-title":"SIAM J. Comput."},{"key":"2023012711542292900_btu463-B10","doi-asserted-by":"crossref","first-page":"W84","DOI":"10.1093\/nar\/gkp373","article-title":"Berkeley phog: phylofacts orthology group prediction web server","volume":"37","author":"Datta","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012711542292900_btu463-B11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-23038-7_8","article-title":"Removing noise from gene trees","author":"Doroftei","year":"2011"},{"key":"2023012711542292900_btu463-B12","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":"2023012711542292900_btu463-B13","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","article-title":"Clustalw and clustalx version 2","volume":"23","author":"Larkin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012711542292900_btu463-B14","doi-asserted-by":"crossref","first-page":"D84","DOI":"10.1093\/nar\/gkr991","article-title":"Ensembl 2012","volume":"40","author":"Flicek","year":"2012","journal-title":"Nucleic Acids Res."},{"issue":"Suppl. 10","key":"2023012711542292900_btu463-B15","first-page":"S14","article-title":"Algorithms: simultaneous error-correction and rooting for gene tree reconciliation and the gene duplication problem","volume":"13","author":"Gorecki","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012711542292900_btu463-B16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-21260-4_17","article-title":"A linear-time algorithm for error-corrected reconciliation of unrooted gene trees","author":"Gorecki","year":"2011"},{"key":"2023012711542292900_btu463-B17","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1080\/10635150390235520","article-title":"A simple, fast and accurate algorithm to estimate large phylogenies by maximum likelihood","volume":"52","author":"Guidon","year":"2003","journal-title":"Syst. Biol."},{"key":"2023012711542292900_btu463-B18","doi-asserted-by":"crossref","first-page":"e197","DOI":"10.1371\/journal.pgen.0030197","article-title":"Gene family evolution across 12 drosophilia genomes","volume":"3","author":"Hahn","year":"2007","journal-title":"PLoS Genet."},{"key":"2023012711542292900_btu463-B19","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s00285-012-0525-x","article-title":"Orthology relations, symbolic ultrametrics, and cographs","volume":"66","author":"Hellmuth","year":"2013","journal-title":"J. Math. Biol."},{"key":"2023012711542292900_btu463-B20","doi-asserted-by":"crossref","first-page":"D556","DOI":"10.1093\/nar\/gkq1109","article-title":"Phylomedb v3.0: an expanding repository of genome-wide collections of trees, alignments and phylogeny-based ozrthology and paralogy predictions","volume":"39","author":"Huerta-Cepas","year":"2011","journal-title":"Nucleic Acids Res."},{"issue":"Suppl. 15","key":"2023012711542292900_btu463-B21","first-page":"S5","article-title":"Gene tree correction guided by orthology","volume":"14","author":"Lafond","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012711542292900_btu463-B22","article-title":"Models and algorithms for genome evolution","volume-title":"Error Detection and Correction of Gene Trees","author":"Lafond","year":"2013"},{"key":"2023012711542292900_btu463-B23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-33122-0_9","article-title":"An optimal reconciliation algorithm for gene trees with polytomies","author":"Lafond","year":"2012"},{"key":"2023012711542292900_btu463-B24","doi-asserted-by":"crossref","first-page":"D377","DOI":"10.1093\/nar\/gks1118","article-title":"Panther in 2013: modeling the evolution of gene function, and other gene attributes, in the context of phylogenetic trees","volume":"41","author":"Mi","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012711542292900_btu463-B25","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":"2023012711542292900_btu463-B26","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1093\/bioinformatics\/btg180","article-title":"MrBayes3: Bayesian phylogenetic inference under mixed models","volume":"19","author":"Ronquist","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012711542292900_btu463-B27","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"2023012711542292900_btu463-B28","doi-asserted-by":"crossref","first-page":"D922","DOI":"10.1093\/nar\/gkt1055","article-title":"Treefam v9: a new website, more species and orthology-on-the-fly","volume":"42","author":"Schreiber","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023012711542292900_btu463-B29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-00982-2_60","article-title":"From gene trees to species trees through a supertree approach","author":"Scornavacca","year":"2009"},{"key":"2023012711542292900_btu463-B30","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1186\/1748-7188-7-31","article-title":"Gene tree correction for reconciliation and species tree inference","volume":"7","author":"Swenson","year":"2012","journal-title":"Algorithms Mol. Biol."},{"key":"2023012711542292900_btu463-B31","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1093\/sysbio\/syt054","article-title":"Efficient exploration of the space of reconciled gene trees","volume":"62","author":"Sz\u00f6llosi","year":"2013","journal-title":"Syst. Biol."},{"key":"2023012711542292900_btu463-B32","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1186\/1748-7188-8-12","article-title":"Reconciliation and local gene tree rearrangement can be of mutual profit","volume":"8","author":"Nguyen","year":"2013","journal-title":"Algorithms Mol. Biol."},{"key":"2023012711542292900_btu463-B33","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1186\/1471-2105-11-312","article-title":"GIGA: a simple, efficient algorithm for gene tree inference in the genomic age","volume":"11","author":"Thomas","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012711542292900_btu463-B34","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":"2023012711542292900_btu463-B35","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":"2023012711542292900_btu463-B36","doi-asserted-by":"crossref","first-page":"i549","DOI":"10.1093\/bioinformatics\/btm193","article-title":"Automatic genome-wide reconstruction of phylogenetic gene trees","volume":"23","author":"Wapinski","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012711542292900_btu463-B37","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1093\/sysbio\/sys076","article-title":"Treefix: statistically informed gene tree error correction using species trees","volume":"62","author":"Wu","year":"2012","journal-title":"Syst. Biol."},{"key":"2023012711542292900_btu463-B38","article-title":"Reconciliation of gene and species trees with polytomies","author":"Zheng","year":"2012"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i519\/48927227\/bioinformatics_30_17_i519.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i519\/48927227\/bioinformatics_30_17_i519.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:28:15Z","timestamp":1674822495000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/17\/i519\/200856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,22]]},"references-count":38,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu463","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,9,1]]},"published":{"date-parts":[[2014,8,22]]}}}