{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:38:21Z","timestamp":1773869901809,"version":"3.50.1"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T00:00:00Z","timestamp":1484006400000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"name":"French Agence Nationale de la Recherche Investissements d\u2019Avenir\/Bioinformatique","award":["ANR-10-BINF-01-01, ANR-10-BINF-01-02, Ancestrome"],"award-info":[{"award-number":["ANR-10-BINF-01-01, ANR-10-BINF-01-02, Ancestrome"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Summary<\/jats:title>\n                    <jats:p>Gene trees reconstructed from sequence alignments contain poorly supported branches when the phylogenetic signal in the sequences is insufficient to determine them all. When a species tree is available, the signal of gains and losses of genes can be used to correctly resolve the unsupported parts of the gene history. However finding a most parsimonious binary resolution of a non-binary tree obtained by contracting the unsupported branches is NP-hard if transfer events are considered as possible gene scale events, in addition to gene origination, duplication and loss. We propose an exact, parameterized algorithm to solve this problem in single-exponential time, where the parameter is the number of connected branches of the gene tree that show low support from the sequence alignment or, equivalently, the maximum number of children of any node of the gene tree once the low-support branches have been collapsed. This improves on the best known algorithm by an exponential factor. We propose a way to choose among optimal solutions based on the available information. We show the usability of this principle on several simulated and biological datasets. The results are comparable in quality to several other tested methods having similar goals, but our approach provides a lower running time and a guarantee that the produced solution is optimal.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and Implementation<\/jats:title>\n                    <jats:p>Our algorithm has been integrated into the ecceTERA phylogeny package, available at http:\/\/mbb.univ-montp2.fr\/MBB\/download_sources\/16__ecceTERA and which can be run online at http:\/\/mbb.univ-montp2.fr\/MBB\/subsection\/softExec.php?soft=eccetera.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw778","type":"journal-article","created":{"date-parts":[[2016,12,2]],"date-time":"2016-12-02T15:07:03Z","timestamp":1480691223000},"page":"980-987","source":"Crossref","is-referenced-by-count":17,"title":["Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses"],"prefix":"10.1093","volume":"33","author":[{"given":"Edwin","family":"Jacox","sequence":"first","affiliation":[{"name":"ISE-M, Universit\u00e9 Montpellier, CNRS, IRD, EPHE, Montpellier, France"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[{"name":"Institut de Biologie Computationnelle (IBC), Montpellier, France"},{"name":"LIRMM, Universit\u00e9 Montpellier, CNRS, Montpellier, France"}]},{"given":"Eric","family":"Tannier","sequence":"additional","affiliation":[{"name":"INRIA Rh\u00f4ne-Alpes, LBBE, Universit\u00e9 Lyon 1, Lyon, France"}]},{"given":"Celine","family":"Scornavacca","sequence":"additional","affiliation":[{"name":"ISE-M, Universit\u00e9 Montpellier, CNRS, IRD, EPHE, Montpellier, France"},{"name":"Institut de Biologie Computationnelle (IBC), Montpellier, France"}]}],"member":"286","published-online":{"date-parts":[[2017,1,5]]},"reference":[{"key":"2023020205004347400_btw778-B1","doi-asserted-by":"crossref","first-page":"i283","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":"2023020205004347400_btw778-B2","author":"Bansal","year":"2014"},{"key":"2023020205004347400_btw778-B3","author":"Chang","year":"2006"},{"key":"2023020205004347400_btw778-B4","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":"2023020205004347400_btw778-B5","first-page":"93","volume-title":"RECOMB International Workshop on Comparative Genomics, Volume 6398 of LNBI","author":"Doyon","year":"2010"},{"key":"2023020205004347400_btw778-B6","doi-asserted-by":"crossref","first-page":"113.","DOI":"10.1186\/1471-2105-5-113","article-title":"Muscle: a multiple sequence alignment method with reduced time and space complexity","volume":"5","author":"Edgar","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023020205004347400_btw778-B7","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2023020205004347400_btw778-B8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1093\/molbev\/msu305","article-title":"Toward more accurate ancestral protein genotype-phenotype reconstructions with the use of species tree-aware gene trees","volume":"32","author":"Groussin","year":"2015","journal-title":"Mol. Biol. Evol"},{"key":"2023020205004347400_btw778-B9","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/sysbio\/syq010","article-title":"New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0","volume":"59","author":"Guindon","year":"2010","journal-title":"Syst. Biol"},{"key":"2023020205004347400_btw778-B10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/sysbio\/syr074","article-title":"Guided tree topology proposals for Bayesian phylogenetic inference","volume":"61","author":"H\u00f6hna","year":"2012","journal-title":"Syst. Biol"},{"key":"2023020205004347400_btw778-B11","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btw105","article-title":"ecceTERA: comprehensive gene tree-species tree reconciliation using parsimony","author":"Jacox","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020205004347400_btw778-B12","first-page":"187","volume-title":"International Symposium on Bioinformatics Research and Applications, Volume 9096 of LNCS","author":"Kordi","year":"2015"},{"key":"2023020205004347400_btw778-B13","first-page":"285","author":"Kordi","year":"2016"},{"key":"2023020205004347400_btw778-B14","doi-asserted-by":"crossref","first-page":"2286","DOI":"10.1093\/bioinformatics\/btp368","article-title":"PhyloBayes 3: a Bayesian software package for phylogenetic reconstruction and molecular dating","volume":"25","author":"Lartillot","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020205004347400_btw778-B15","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1093\/oso\/9780198566106.003.0014","volume-title":"Mathematics of Evolution and Phylogeny","author":"Mossel","year":"2005"},{"key":"2023020205004347400_btw778-B16","doi-asserted-by":"crossref","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":"2023020205004347400_btw778-B17","doi-asserted-by":"crossref","first-page":"e0159559.","DOI":"10.1371\/journal.pone.0159559","article-title":"Efficient gene tree correction guided by genome evolution","volume":"11","author":"Noutahi","year":"2016","journal-title":"PLoS ONE"},{"key":"2023020205004347400_btw778-B18","doi-asserted-by":"crossref","first-page":"S3.","DOI":"10.1186\/1471-2105-10-S6-S3","article-title":"Databases of homologous gene families for comparative genomics","volume":"10","author":"Penel","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023020205004347400_btw778-B19","first-page":"235","article-title":"Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees","volume":"13","author":"Rambaut","year":"1997","journal-title":"Comput. Appl. Biosci. CABIOS"},{"key":"2023020205004347400_btw778-B20","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1093\/bioinformatics\/btu728","article-title":"Joint amalgamation of most parsimonious reconciled gene trees","volume":"31","author":"Scornavacca","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020205004347400_btw778-B21","doi-asserted-by":"crossref","first-page":"1246","DOI":"10.1093\/bioinformatics\/17.12.1246","article-title":"CONSEL: for assessing the confidence of phylogenetic tree selection","volume":"17","author":"Shimodaira","year":"2001","journal-title":"Bioinformatics"},{"key":"2023020205004347400_btw778-B22","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1093\/sysbio\/syu007","article-title":"A Bayesian method for analyzing lateral gene transfer","volume":"63","author":"Sj\u00f6strand","year":"2014","journal-title":"Syst. Biol"},{"key":"2023020205004347400_btw778-B23","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/bioinformatics\/btu033","article-title":"RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies","volume":"30","author":"Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020205004347400_btw778-B24","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\u00f6ll\u0151si","year":"2013","journal-title":"Syst. Biol"},{"key":"2023020205004347400_btw778-B25","doi-asserted-by":"crossref","first-page":"e42","DOI":"10.1093\/sysbio\/syu048","article-title":"The inference of gene trees with species trees","volume":"64","author":"Sz\u00f6ll\u0151si","year":"2015","journal-title":"Syst. Biol"},{"key":"2023020205004347400_btw778-B26","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1089\/cmb.2014.0021","article-title":"Are the duplication cost and robinson-foulds distance equivalent?","volume":"21","author":"Zheng","year":"2014","journal-title":"J. Comput. Biol"},{"key":"2023020205004347400_btw778-B27","author":"Zheng","year":"2014"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/7\/980\/49038373\/bioinformatics_33_7_980.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/7\/980\/49038373\/bioinformatics_33_7_980.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T19:49:24Z","timestamp":1718912964000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/7\/980\/2883389"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2017,1,5]]},"references-count":27,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2017,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw778","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/064675","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,4,1]]},"published":{"date-parts":[[2017,1,5]]}}}