FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix

By Morgan N. Price, Paramvir S. Dehal, Adam P. Arkin. Molecular biology and evolution, 2009

5,061 citations recorded by the source corpus.

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(N2) space and O(N2L) time, but FastTree requires just O(NLa + N) memory and O(Nlog (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.

Subfields: Molecular Biology, Plant Science

View Paper: https://www.semanticscholar.org/paper/9d054caaec9e59a15b30845f81d31dcf95594b87

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Plant Science

Citations in the corpus

Real-Time Whole-Genome Sequencing for Routine Typing, Surveillance, and Outbreak Detection of Verotoxigenic Escherichia coli (2014, methodology): “In addition, for further comparison of the phylogenetic approaches, a phyloge- netic tree based on the NDtree matrix, but with positions called in all of the sequences, and constructed using Fastree, is included in Dataset S4.”
Differential Growth Responses of Soil Bacterial Taxa to Carbon Substrates of Varying Chemical Recalcitrance (2011, methodology): “, 2006a) and local bootstrapped neighbor-joining trees constructed using FastTree(2) with default settings (Price et al., 2009).”
Human oral, gut, and plaque microbiota in patients with atherosclerosis (2010, methodology): “Price MN, Dehal PS, Arkin AP (2009) FastTree: Computing large minimum evolution trees with profiles instead of a distance matrix.”
Metagenomic analysis of a permafrost microbial community reveals a rapid response to thaw (2011, methodology): “The phylogeny of cluster representatives was inferred using an approximate maximum likelihood method designed for large alignments as implemented by the software FastTre”
Responses of soil bacterial and fungal communities to extreme desiccation and rewetting (2013, methodology): “1 (Price et al., 2009), after aligning the representative sequences against the greengenes core set using the NAST algorithm (75% minimum sequence similarity, 200 nt minimum length, no gap character removal) on the greengenes website (DeSantis et al.”
FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments (2010, methodology): “The simulated protein alignments and the genuine COG alignments were described previously [2].”
Tracking microbial colonization in fecal microbiota transplantation experiments via genome-resolved metagenomics (2017, neutral): “FastTree: computing large minimum evolution trees with profiles instead of a distance matrix.”
Advancing our understanding of the human microbiome using QIIME (2013, methodology): “The current methods supported for inferring the phylogenetic tree in QIIME are FastTree (Price, Dehal, & Arkin, 2009), clearcut (Evans, Sheneman, & Foster, 2006), clustalw (Larkin et al., 2007), raxml (Stamatakis, Ludwig, &Meier, 2005), andmuscle (Edgar, 2004).”
Diversity and heritability of the maize rhizosphere microbiome under field conditions (2013, methodology): “A phylogenetic tree was built using FastTree (7).”
Human Gut Microbiota from Autism Spectrum Disorder Promote Behavioral Symptoms in Mice (2019, methodology): “Subsequently, fragments were inserted to 16S rRNA gene context by q2-fragment-insertion (Janssen et al., 2018) and alignments were obtained using MAFFT (Yamada et al., 2016) and a phylogenetic tree was generated using FastTree (Price et al., 2009).”
Consistent effects of nitrogen amendments on soil microbial communities and processes across biomes (2012, methodology): “A phylogenetic tree containing the aligned sequences was then produced using FastTree (Price et al. , 2009).”