FastRFS: fast and accurate Robinson-Foulds Supertrees using constrained exact optimization.
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.



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.



FastRFS is available on github at https://github.com/pranjalv123/FastRFS.



warnow@illinois.edu.



Supplementary data are available at Bioinformatics online.
Department of Computer Science.
Pranjal
P
Vachaspati
Department of Computer Science.|National Center for Supercomputing Applications.|Department of Bioengineering, University of Illinois, Urbana-Champaign, Urbana, IL 61801, USA.
Tandy
T
Warnow
D000465:Algorithms; D000818:Animals; D001499:Bayes Theorem; D023281:Genomics / Q000379:methods*; D006801:Humans; D016013:Likelihood Functions; D010802:Phylogeny
R Soc Open Sci. 2015 Aug 05;2(8):140436
26361544
Syst Biol. 2008 Apr;57(2):243-50
18398769
Bioinformatics. 2015 Jun 15;31(12):i44-52
26072508
Bioinformatics. 2014 May 1;30(9):1312-3
24451623
PLoS Comput Biol. 2009 Sep;5(9):e1000501
19749978
Syst Biol. 2012 Mar;61(2):214-27
21934137
Bioinformatics. 2015 Feb 1;31(3):432-3
25273112
BMC Genomics. 2015;16 Suppl 10:S3
26449326
J Comput Biol. 2002;9(5):687-705
12487758
Algorithms Mol Biol. 2010 Jan 04;5:8
20047664
Pac Symp Biocomput. 2013;:250-61
23424130
BMC Evol Biol. 2011 Jul 13;11:205
21752249
J Comput Biol. 2011 Nov;18(11):1543-59
22035329
Syst Biol. 2006 Oct;55(5):818-36
17060202
Bioinformatics. 2014 Sep 1;30(17):i541-8
25161245
BMC Genomics. 2014;15 Suppl 6:S7
25572610
Philos Trans R Soc Lond B Biol Sci. 2015 Sep 26;370(1678):20140337
26323767
Bioinformatics. 2012 Jun 15;28(12):i274-82
22689772
Algorithms Mol Biol. 2010 Feb 24;5:18
20181274
J Comput Biol. 1999 Fall-Winter;6(3-4):369-86
10582573
Algorithms Mol Biol. 2012 Jan 26;7(1):3
22280525
BMC Bioinformatics. 2008 Mar 26;9:166
18366787
Syst Biol. 2016 May;65(3):397-416
25281847
BMC Bioinformatics. 2014 Jun 12;15:183
24925766
IEEE/ACM Trans Comput Biol Bioinform. 2009 Jul-Sep;6(3):420-6
19644170
BMC Evol Biol. 2006 Nov 13;6:93
17101039