{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:09:09Z","timestamp":1769843349979,"version":"3.49.0"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2016,11,16]],"date-time":"2016-11-16T00:00:00Z","timestamp":1479254400000},"content-version":"vor","delay-in-days":54,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Debra and Ira Cohen Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The estimation of phylogenetic trees is a major part of many biological dataset analyses, but maximum likelihood approaches are NP-hard and Bayesian MCMC methods do not scale well to even moderate-sized datasets. Supertree methods, which are used to construct trees from trees computed on subsets, are critically important tools for enabling the statistical estimation of phylogenies for large and potentially heterogeneous datasets. Supertree estimation is itself NP-hard, and no current supertree method has sufficient accuracy and scalability to provide good accuracy on the large datasets that supertree methods were designed for, containing thousands of species and many subset trees.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present FastRFS, a new method based on a dynamic programming method we have developed to find an exact solution to the Robinson-Foulds Supertree problem within a constrained search space. FastRFS has excellent accuracy in terms of criterion scores and topological accuracy of the resultant trees, substantially improving on competing methods on a large collection of biological and simulated data. In addition, FastRFS is extremely fast, finishing in minutes on even very large datasets, and in under an hour on a biological dataset with 2228 species.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and Implementation<\/jats:title>\n                  <jats:p>FastRFS is available on github at https:\/\/github.com\/pranjalv123\/FastRFS<\/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\/btw600","type":"journal-article","created":{"date-parts":[[2016,9,24]],"date-time":"2016-09-24T01:11:09Z","timestamp":1474679469000},"page":"631-639","source":"Crossref","is-referenced-by-count":35,"title":["FastRFS: fast and accurate Robinson-Foulds Supertrees using constrained exact optimization"],"prefix":"10.1093","volume":"33","author":[{"given":"Pranjal","family":"Vachaspati","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, IL, USA"},{"name":"National Center for Supercomputing Applications, University of Illinois, Urbana-Champaign, Urbana, IL, USA"},{"name":"Department of Bioengineering, University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,9,23]]},"reference":[{"key":"2023020204430324300_btw600-B1","doi-asserted-by":"crossref","first-page":"183.","DOI":"10.1186\/1471-2105-15-183","article-title":"L.U.-st: a tool for approximated maximum likelihood supertree reconstruction","volume":"15","author":"Akanni","year":"2014","journal-title":"BMC Bioinf"},{"key":"2023020204430324300_btw600-B2","doi-asserted-by":"crossref","first-page":"20140337.","DOI":"10.1098\/rstb.2014.0337","article-title":"Horizontal gene transfer from Eubacteria to Archaebacteria and what it means for our understanding of eukaryogenesis","volume":"370","author":"Akanni","year":"2015","journal-title":"Philos. Trans. R. Soc. B"},{"key":"2023020204430324300_btw600-B3","doi-asserted-by":"crossref","first-page":"140436.","DOI":"10.1098\/rsos.140436","article-title":"Implementing and testing Bayesian and maximum-likelihood supertree methods in phylogenetics","volume":"2","author":"Akanni","year":"2015","journal-title":"R. Soc. Open Sci"},{"key":"2023020204430324300_btw600-B4","doi-asserted-by":"crossref","first-page":"18.","DOI":"10.1186\/1748-7188-5-18","article-title":"Robinson-Foulds supertrees","volume":"5","author":"Bansal","year":"2010","journal-title":"Algorithms Mol. Biol"},{"key":"2023020204430324300_btw600-B5","author":"Bayzid","year":"2013"},{"key":"2023020204430324300_btw600-B6","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1471-2164-15-S6-S7","article-title":"Disk covering methods improve phylogenomic analyses","volume":"15","author":"Bayzid","year":"2014","journal-title":"BMC Genomics"},{"key":"2023020204430324300_btw600-B7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1186\/1471-2148-6-93","article-title":"A higher-level MRP supertree of placental mammals","volume":"6","author":"Beck","year":"2006","journal-title":"BMC Evol. Biol"},{"key":"2023020204430324300_btw600-B8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4020-2330-9","volume-title":"Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life.","author":"Bininda-Emonds","year":"2004"},{"key":"2023020204430324300_btw600-B9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1006\/jagm.2000.1133","article-title":"Constructing optimal trees from quartets","volume":"38","author":"Bryant","year":"2001","journal-title":"J. Algorithms"},{"key":"2023020204430324300_btw600-B10","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1109\/TCBB.2009.32","article-title":"Computing the distribution of a tree metric","volume":"6","author":"Bryant","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023020204430324300_btw600-B11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1017\/S0952836904005539","article-title":"A species-level phylogenetic supertree of marsupials","volume":"264","author":"Cardillo","year":"2004","journal-title":"J. Zool"},{"key":"2023020204430324300_btw600-B12","article-title":"MulRF: a software package for phylogenetic analysis using multi-copy gene trees","author":"Chaudhary","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020204430324300_btw600-B13","doi-asserted-by":"crossref","first-page":"166.","DOI":"10.1186\/1471-2105-9-166","article-title":"Fast NJ-like algorithms to deal with incomplete distance matrices","volume":"9","author":"Criscuolo","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020204430324300_btw600-B14","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1089\/106652702761034136","article-title":"Fast and accurate phylogeny minimum-evolution principle","volume":"9","author":"Desper","year":"2002","journal-title":"J. Comput. Biol"},{"key":"2023020204430324300_btw600-B15","author":"Hallett","year":"2000"},{"key":"2023020204430324300_btw600-B16","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1089\/106652799318337","article-title":"Disk-covering, a fast converging method for phylogenetic tree reconstruction","volume":"6","author":"Huson","year":"1999","journal-title":"J. Comput. Biol"},{"key":"2023020204430324300_btw600-B17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1093\/auk\/119.1.88","article-title":"Seabird supertrees: combining partial estimates of procellariiform phylogeny","volume":"119","author":"Kennedy","year":"2002","journal-title":"Auk"},{"key":"2023020204430324300_btw600-B18","doi-asserted-by":"crossref","first-page":"205.","DOI":"10.1186\/1471-2148-11-205","article-title":"Split-based computation of majority-rule supertrees","volume":"11","author":"Kupczok","year":"2011","journal-title":"BMC Evol. Biol"},{"key":"2023020204430324300_btw600-B19","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1093\/sysbio\/syu082","article-title":"A Bayesian supertree model for genome-wide species tree reconstruction","volume":"65","author":"Martins","year":"2016","journal-title":"Syst. Biol"},{"key":"2023020204430324300_btw600-B20","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1080\/10635150600999150","article-title":"Phylogenetic supermatrix analysis of GenBank sequences from 2228 papilionoid legumes","volume":"55","author":"McMahon","year":"2006","journal-title":"Syst. Biol"},{"key":"2023020204430324300_btw600-B21","year":"2015"},{"key":"2023020204430324300_btw600-B22","doi-asserted-by":"crossref","first-page":"i44","DOI":"10.1093\/bioinformatics\/btv234","article-title":"ASTRAL-II: coalescent-based species tree estimation with many hundreds of taxa and thousands of genes","volume":"31","author":"Mirarab","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020204430324300_btw600-B23","doi-asserted-by":"crossref","first-page":"i541","DOI":"10.1093\/bioinformatics\/btu462","article-title":"ASTRAL: genome-scale coalescent-based species tree estimation","volume":"30","author":"Mirarab","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020204430324300_btw600-B24","doi-asserted-by":"crossref","first-page":"i274","DOI":"10.1093\/bioinformatics\/bts218","article-title":"DACTAL: divide-and-conquer trees (almost) without alignments","volume":"28","author":"Nelesen","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020204430324300_btw600-B25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-7-3","article-title":"MRL and SuperFine+ MRL: new supertree methods","volume":"7","author":"Nguyen","year":"2012","journal-title":"Algorithms Mol. Biol"},{"key":"2023020204430324300_btw600-B26","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci"},{"key":"2023020204430324300_btw600-B27","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":"2023020204430324300_btw600-B28","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1080\/10635150802033014","article-title":"Maximum likelihood supertrees","volume":"57","author":"Steel","year":"2008","journal-title":"Syst. Biol"},{"key":"2023020204430324300_btw600-B29","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1748-7188-5-8","article-title":"A simulation study comparing supertree and combined analysis methods using SMIDGen","volume":"5","author":"Swenson","year":"2010","journal-title":"Algorithms Mol. Biol"},{"key":"2023020204430324300_btw600-B30","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1093\/sysbio\/syr092","article-title":"SuperFine: fast and accurate supertree estimation","volume":"61","author":"Swenson","year":"2012","journal-title":"Syst. Biol"},{"key":"2023020204430324300_btw600-B31","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":"2023020204430324300_btw600-B32","doi-asserted-by":"crossref","first-page":"S3.","DOI":"10.1186\/1471-2164-16-S10-S3","article-title":"ASTRID: Accurate species trees from internode distances","volume":"16","author":"Vachaspati","year":"2015","journal-title":"BMC Genomics"},{"key":"2023020204430324300_btw600-B33","author":"Warnow","year":"2001"},{"key":"2023020204430324300_btw600-B34","first-page":"277","article-title":"Molecular phylogeny of the \"temperate herbaceous tribes\" of papilionoid legumes: a supertree approach","volume":"9","author":"Wojciechowski","year":"2000","journal-title":"Adv. Legume Syst"},{"key":"2023020204430324300_btw600-B35","first-page":"1543","article-title":"Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles","volume":"18","author":"Yu","year":"2011","journal-title":"J. Comput. Biol. (Special Issue for RECOMB 2011)"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/5\/631\/49037898\/bioinformatics_33_5_631.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/5\/631\/49037898\/bioinformatics_33_5_631.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T04:48:18Z","timestamp":1675313298000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/5\/631\/2525708"}},"subtitle":[],"editor":[{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2016,9,23]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw600","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,3,1]]},"published":{"date-parts":[[2016,9,23]]}}}