FastTree 2--approximately Maximum-likelihood Trees for Large Alignments

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2010 Mar 13

PMID 20224823

Citations 6699

Authors

Morgan N Price

Paramvir S Dehal

Adam P Arkin

Affiliations

Soon will be listed here.

Abstract

Background: We recently described FastTree, a tool for inferring phylogenies for alignments with up to hundreds of thousands of sequences. Here, we describe improvements to FastTree that improve its accuracy without sacrificing scalability.

Methodology/principal Findings: Where FastTree 1 used nearest-neighbor interchanges (NNIs) and the minimum-evolution criterion to improve the tree, FastTree 2 adds minimum-evolution subtree-pruning-regrafting (SPRs) and maximum-likelihood NNIs. FastTree 2 uses heuristics to restrict the search for better trees and estimates a rate of evolution for each site (the "CAT" approximation). Nevertheless, for both simulated and genuine alignments, FastTree 2 is slightly more accurate than a standard implementation of maximum-likelihood NNIs (PhyML 3 with default settings). Although FastTree 2 is not quite as accurate as methods that use maximum-likelihood SPRs, most of the splits that disagree are poorly supported, and for large alignments, FastTree 2 is 100-1,000 times faster. FastTree 2 inferred a topology and likelihood-based local support values for 237,882 distinct 16S ribosomal RNAs on a desktop computer in 22 hours and 5.8 gigabytes of memory.

Conclusions/significance: FastTree 2 allows the inference of maximum-likelihood phylogenies for huge alignments. FastTree 2 is freely available at http://www.microbesonline.org/fasttree.

Citing Articles

Diversity and functional features of the root-associated bacteriome are dependent on grapevine susceptibility to Plasmopara viticola.

Duret M, Wallner A, Besaury L, Aziz A Environ Microbiome. 2025; 20(1):30.

PMID: 40087775 DOI: 10.1186/s40793-025-00690-w.

Genome mining the black-yeast Aureobasidium pullulans NRRL 62031 for biotechnological traits.

Xiao D, Driller M, Stein K, Blank L, Tiso T BMC Genomics. 2025; 26(1):244.

PMID: 40082747 PMC: 11905612. DOI: 10.1186/s12864-025-11395-2.

Integration of therapeutic cargo into the human genome with programmable type V-K CAST.

Liu J, Aliaga Goltsman D, Alexander L, Khayi K, Hong J, Dunham D Nat Commun. 2025; 16(1):2427.

PMID: 40082411 PMC: 11906591. DOI: 10.1038/s41467-025-57416-2.

Diversity and Structure of the Prokaryotic Community in Tropical Monomictic Reservoir.

Barjau-Aguilar M, Reyes-Hernandez A, Merino-Ibarra M, Vilaclara G, Ramirez-Zierold J, Alcantara-Hernandez R Microb Ecol. 2025; 88(1):12.

PMID: 40072582 PMC: 11903632. DOI: 10.1007/s00248-025-02508-1.

Niche partitioning of microbial communities at an ancient vitrified hillfort: implications for vitrified radioactive waste disposal.

Plymale A, Wells J, Pearce C, Brislawn C, Graham E, Cheeke T Int Biodeterior Biodegradation. 2025; 38(1).

PMID: 40070387 PMC: 11894924. DOI: 10.1080/01490451.2020.1807658.

References

Stamatakis A . RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics. 2006; 22(21):2688-90. DOI: 10.1093/bioinformatics/btl446. View

DeSantis T, Hugenholtz P, Larsen N, Rojas M, Brodie E, Keller K . Greengenes, a chimera-checked 16S rRNA gene database and workbench compatible with ARB. Appl Environ Microbiol. 2006; 72(7):5069-72. PMC: 1489311. DOI: 10.1128/AEM.03006-05. View

Stoye J, Evers D, Meyer F . Rose: generating sequence families. Bioinformatics. 1998; 14(2):157-63. DOI: 10.1093/bioinformatics/14.2.157. View

Bradley R, Roberts A, Smoot M, Juvekar S, Do J, Dewey C . Fast statistical alignment. PLoS Comput Biol. 2009; 5(5):e1000392. PMC: 2684580. DOI: 10.1371/journal.pcbi.1000392. View

Nei M, Kumar S, Takahashi K . The optimization principle in phylogenetic analysis tends to give incorrect topologies when the number of nucleotides or amino acids used is small. Proc Natl Acad Sci U S A. 1998; 95(21):12390-7. PMC: 22842. DOI: 10.1073/pnas.95.21.12390. View

Saitou N, Nei M . The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987; 4(4):406-25. DOI: 10.1093/oxfordjournals.molbev.a040454. View

Shimodaira H, Hasegawa M . CONSEL: for assessing the confidence of phylogenetic tree selection. Bioinformatics. 2001; 17(12):1246-7. DOI: 10.1093/bioinformatics/17.12.1246. View

Felsenstein J . CONFIDENCE LIMITS ON PHYLOGENIES: AN APPROACH USING THE BOOTSTRAP. Evolution. 2017; 39(4):783-791. DOI: 10.1111/j.1558-5646.1985.tb00420.x. View

Desper R, Gascuel O . Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J Comput Biol. 2002; 9(5):687-705. DOI: 10.1089/106652702761034136. View

10.

Sonnhammer E, Hollich V . Scoredist: a simple and robust protein sequence distance estimator. BMC Bioinformatics. 2005; 6:108. PMC: 1131889. DOI: 10.1186/1471-2105-6-108. View

11.

Gascuel O . BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data. Mol Biol Evol. 1997; 14(7):685-95. DOI: 10.1093/oxfordjournals.molbev.a025808. View

12.

Bordewich M, Gascuel O, Huber K, Moulton V . Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference. IEEE/ACM Trans Comput Biol Bioinform. 2009; 6(1):110-7. DOI: 10.1109/TCBB.2008.37. View

13.

Desper R, Gascuel O . Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting. Mol Biol Evol. 2003; 21(3):587-98. DOI: 10.1093/molbev/msh049. View

14.

Tatusov R, Natale D, Garkavtsev I, Tatusova T, Shankavaram U, Rao B . The COG database: new developments in phylogenetic classification of proteins from complete genomes. Nucleic Acids Res. 2000; 29(1):22-8. PMC: 29819. DOI: 10.1093/nar/29.1.22. View

15.

Studier J, Keppler K . A note on the neighbor-joining algorithm of Saitou and Nei. Mol Biol Evol. 1988; 5(6):729-31. DOI: 10.1093/oxfordjournals.molbev.a040527. View

16.

Hordijk W, Gascuel O . Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood. Bioinformatics. 2005; 21(24):4338-47. DOI: 10.1093/bioinformatics/bti713. View

17.

Guindon S, Gascuel O . A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Syst Biol. 2003; 52(5):696-704. DOI: 10.1080/10635150390235520. View

18.

Anisimova M, Gascuel O . Approximate likelihood-ratio test for branches: A fast, accurate, and powerful alternative. Syst Biol. 2006; 55(4):539-52. DOI: 10.1080/10635150600755453. View

19.

Roch S . A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE/ACM Trans Comput Biol Bioinform. 2006; 3(1):92-4. DOI: 10.1109/TCBB.2006.4. View

20.

Price M, Dehal P, Arkin A . FastTree: computing large minimum evolution trees with profiles instead of a distance matrix. Mol Biol Evol. 2009; 26(7):1641-50. PMC: 2693737. DOI: 10.1093/molbev/msp077. View