FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix
Open accessThe DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Abstract
Gene families are growing rapidly, but standard methods for inferring phylogenies do not scale to alignments with over 10,000 sequences. We present FastTree, a method for constructing large phylogenies and for estimating their reliability. Instead of storing a distance matrix, FastTree stores sequence profiles of internal nodes in the tree. FastTree uses these profiles to implement Neighbor-Joining and uses heuristics to quickly identify candidate joins. FastTree then uses nearest neighbor interchanges to reduce the length of the tree. For an alignment with N sequences, L sites, and a different characters, a distance matrix requires O(N(2)) space and O(N(2)L) time, but FastTree requires just O(NLa + N ) memory and O(N log (N)La) time. To estimate the tree's reliability, FastTree uses local bootstrapping, which gives another 100-fold speedup over a distance matrix. For example, FastTree computed a tree and support values for 158,022 distinct 16S ribosomal RNAs in 17 h and 2.4 GB of memory. Just computing pairwise Jukes-Cantor distances and storing them, without inferring a tree or bootstrapping, would require 17 h and 50 GB of memory. In simulations, FastTree was slightly more accurate than Neighbor-Joining, BIONJ, or FastME; on genuine alignments, FastTree's topologies had higher likelihoods. FastTree is available at http://microbesonline.org/fasttree.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures


Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The neighbor-joining method: a new method for reconstructing phylogenetic trees.
(1987) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040454 · Cited by 59,715
MUSCLE: multiple sequence alignment with high accuracy and high throughput
Edgar, R. C. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh340 · Cited by 44,662
CONFIDENCE LIMITS ON PHYLOGENIES: AN APPROACH USING THE BOOTSTRAP
Felsenstein, J. (1985) · Evolution · doi:10.1111/j.1558-5646.1985.tb00420.x · Cited by 44,647
DeLong, E. R., DeLong, D. M., & Clarke-Pearson, D. L. (1988) · Biometrics · doi:10.2307/2531595 · Cited by 22,649
Confidence Limits on Phylogenies: An Approach Using the Bootstrap
Felsenstein, J. (1985) · Evolution · doi:10.2307/2408678 · Cited by 19,371
A Simple, Fast, and Accurate Algorithm to Estimate Large Phylogenies by Maximum Likelihood
Guindon, S., & Gascuel, O. (2003) · Systematic Biology · doi:10.1080/10635150390235520 · Cited by 16,806
RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models
Stamatakis, A. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl446 · Cited by 15,582
Greengenes, a Chimera-Checked 16S rRNA Gene Database and Workbench Compatible with ARB
DeSantis, T. Z., Hugenholtz, P., Larsen, N., Rojas, M., Brodie, E. L., Keller, K., Huber, T., Dalevi, D., Hu, P., & Andersen, G. L. (2006) · Applied and Environmental Microbiology · doi:10.1128/aem.03006-05 · Cited by 10,891
Amino acid substitution matrices from protein blocks.
Henikoff, S., & Henikoff, J. G. (1992) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.89.22.10915 · Cited by 6,218
Approximate likelihood-ratio test for branches: A fast, accurate, and powerful alternative
Anisimova, M., & Gascuel, O. (2006) · Systematic Biology · doi:10.1080/10635150600755453 · Cited by 2,693
Pfam: clans, web tools and services
Finn, R. D. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj149 · Cited by 2,302
The COG database: new developments in phylogenetic classification of proteins from complete genomes
Tatusov, R. L. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.22 · Cited by 1,895
BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data
Gascuel, O. (1997) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a025808 · Cited by 1,836
Schaffer, A. A. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.14.2994 · Cited by 1,386
Increased Taxon Sampling Greatly Reduces Phylogenetic Error
Zwickl, D. J., & Hillis, D. M. (2002) · Systematic Biology · doi:10.1080/10635150290102339 · Cited by 939
Maximum likelihood inference of protein phylogeny and the origin of chloroplasts
Kishino, H., Miyata, T., & Hasegawa, M. (1990) · Journal of Molecular Evolution · doi:10.1007/bf02109483 · Cited by 883
Bootstrap confidence levels for phylogenetic trees.
Efron, B., Halloran, E., & Holmes, S. (1996) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.93.14.7085 · Cited by 696
Phylogenomics: Improving Functional Predictions for Uncharacterized Genes by Evolutionary Analysis
Eisen, J. A. (1998) · Genome Research · doi:10.1101/gr.8.3.163 · Cited by 640
Bootstrap confidence levels for phylogenetic trees
Efron, B., Halloran, E., & Holmes, S. (1996) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.93.23.13429 · Cited by 548
TreeFam: a curated database of phylogenetic trees of animal gene families
Li, H. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj118 · Cited by 523
Tolerating some redundancy significantly speeds up clustering of large protein databases
Li, W., Jaroszewski, L., & Godzik, A. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.1.77 · Cited by 516
Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle
Desper, R., & Gascuel, O. (2002) · Journal of Computational Biology · doi:10.1089/106652702761034136 · Cited by 488
A note on the neighbor-joining algorithm of Saitou and Nei.
(1988) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040527 · Cited by 445
Gascuel, O. (2006) · Molecular Biology and Evolution · doi:10.1093/molbev/msl072 · Cited by 358
Quantitative Phylogenetic Assessment of Microbial Communities in Diverse Environments
von Mering, C., Hugenholtz, P., Raes, J., Tringe, S. G., Doerks, T., Jensen, L. J., Ward, N., & Bork, P. (2007) · Science · doi:10.1126/science.1133420 · Cited by 346
QuickTree: building huge Neighbour-Joining trees of protein sequences
Howe, K., Bateman, A., & Durbin, R. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.11.1546 · Cited by 300
Rose: generating sequence families.
Stoye, J., Evers, D., & Meyer, F. (1998) · Bioinformatics · doi:10.1093/bioinformatics/14.2.157 · Cited by 265
The MicrobesOnline Web site for comparative genomics
Alm, E. J., Huang, K. H., Price, M. N., Koche, R. P., Keller, K., Dubchak, I. L., & Arkin, A. P. (2005) · Genome Research · doi:10.1101/gr.3844805 · Cited by 204
Self-citationProtein Molecular Function Prediction by Bayesian Phylogenomics
Engelhardt, B. E., Jordan, M. I., Muratore, K. E., & Brenner, S. E. (2005) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0010045 · Cited by 196
Nei, M., Kumar, S., & Takahashi, K. (1998) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.95.21.12390 · Cited by 192
Simonsen, M., Mailund, T., & Pedersen, C. N. S. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87361-7_10 · Cited by 177
Relaxed Neighbor Joining: A Fast Distance-Based Phylogenetic Tree Construction Method
Evans, J., Sheneman, L., & Foster, J. A. (2006) · Journal of Molecular Evolution · doi:10.1007/s00239-005-0176-2 · Cited by 152
Scoredist: A simple and robust protein sequence distance estimator
Sonnhammer, E. L. L., & Hollich, V. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-108 · Cited by 120
PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences
Katoh, K., & Toh, H. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl592 · Cited by 105
A phylogenomic gene cluster resource: the Phylogenetically Inferred Groups (PhIGs) database
Dehal, P., & Boore, J. L. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-201 · Cited by 89
Self-citationRecrafting the neighbor-joining method
Mailund, T., Brodal, G. S., Fagerberg, R., Pedersen, C. N., & Phillips, D. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-29 · Cited by 63
SCALING OF ACCURACY IN EXTREMELY LARGE PHYLOGENETIC TREES
Bininda‐Emonds, O. R. P., Brady, S. G., Kim, J., & Sanderson, M. J. (2000) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789814447362_0053 · Cited by 56
Müller, T., Rahmann, S., Dandekar, T., et al. (2004) · BMC Evolutionary Biology · doi:10.1186/1471-2148-4-20 · Cited by 56
Accurate and scalable identification of functional sites by evolutionary tracing
Lichtarge, O., Yao, H., Kristensen, D. M., et al. (2003) · Journal of Structural and Functional Genomics · doi:10.1023/a:1026115125950 · Cited by 43
Elias, I., & Lagergren, J. (2005) · Lecture notes in computer science · doi:10.1007/11523468_102 · Cited by 40
Hollich, V., Milchert, L., Arvestad, L., & Sonnhammer, E. L. L. (2005) · Molecular Biology and Evolution · doi:10.1093/molbev/msi224 · Cited by 25
Accelerating the Neighbor-Joining Algorithm Using the Adaptive Bucket Data Structure
Zaslavsky, L. Y., & Tatusova, T. A. (2008) · Springer eBooks · doi:10.1007/978-3-540-79450-9_12 · Cited by 7
Research works printed but not linked: 4
- 2001, Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing, 2001, 547
- 1998, 44, 837
- Saitou, 1987, Molecular Biology and Evolution, 4, 406
- Studier, 1988, Molecular Biology and Evolution, 5, 729
Cited by
FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments
Price, M. N., Dehal, P. S., & Arkin, A. P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0009490 · Cited by 14,894
Self-citationThe Pfam Protein Families Database
Bateman, A. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.1.276 · Cited by 14,000
Parks, D. H., Imelfort, M., Skennerton, C. T., Hugenholtz, P., & Tyson, G. W. (2015) · Genome Research · doi:10.1101/gr.186072.114 · Cited by 12,496
Global patterns of 16S rRNA diversity at a depth of millions of sequences per sample
Caporaso, J. G., Lauber, C. L., Walters, W. A., Berg-Lyons, D., Lozupone, C. A., Turnbaugh, P. J., Fierer, N., & Knight, R. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1000080107 · Cited by 9,711
Dominguez-Bello, M. G., Costello, E. K., Contreras, M., Magris, M., Hidalgo, G., Fierer, N., & Knight, R. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1002601107 · Cited by 4,774
Metadata
- Authors
- Price, M. N., Dehal, P. S., & Arkin, A. P.
- Affiliations
- Lawrence Berkeley National Laboratory (US)
- Corresponding author
- Price, M. N.
- Dehal, P. S.
- Arkin, A. P.
- Venue
- Molecular Biology and Evolution
- Publisher
- Oxford University Press (OUP)
- Published
- 2009-04-17
- Volume
- 26
- Issue
- 7
- Pages
- 1641-1650
- ISSN
- 0737-4038 (ISSN-L)
- 1537-1719
- PMC
- PMC2693737
- OpenAlex
- W2105329815
- Semantic Scholar
- 9d054caaec9e59a15b30845f81d31dcf95594b87
- Cited by
- 5,602
- References
- 42
- Citations by year
- 2026: 460 · 2025: 573 · 2024: 638 · 2023: 571 · 2022: 496 · 2021: 511 · 2020: 503 · 2019: 393 · 2018: 314 · 2017: 279 · 2016: 227 · 2015: 182 · 2014: 143 · 2013: 112 · 2012: 77
- FWCI
- 25.69
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Licence
- cc-by-nc
- Locations
- Molecular Biology and Evolution (publishedVersion)
- PubMed Central (publishedVersion, cc-by-nc)
- PubMed (publishedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- University of North Texas Digital Library (University of North Texas) (submittedVersion)
- eScholarship (California Digital Library) (submittedVersion)
- Lawrence Berkeley National Laboratory
- Funders
- U.S. Department of Energy (-AC02-05CH11231, 05CH11231, DE AC02 05CH11231, DE-AC02-)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › RNA and protein synthesis mechanisms
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- FastTree, phylogenetic tree construction, minimum evolution, sequence profiles, neighbor-joining, 16S rRNA, nearest neighbor interchange
- MeSH terms
- Algorithms, Models, Genetic, Phylogeny, Proteins, Sequence Alignment, Evolution, Molecular
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.