FastTree

FastTree constructs approximately-maximum-likelihood phylogenetic trees from nucleotide or protein sequence alignments to enable phylogenetic inference on large-scale sequence datasets.

Key Features:

• Approximately-maximum-likelihood inference: Performs approximately-maximum-likelihood phylogenetic inference from nucleotide or protein alignments.
• Support for nucleotide and protein sequences: Accepts alignments of nucleotide or protein sequences for tree reconstruction.
• Scalability: Handles alignments containing hundreds of thousands of sequences for large-scale analyses.
• Efficient memory usage: Stores sequence profiles at internal nodes instead of an O(N^2) distance matrix, reducing memory requirements to O(NLa + N) where N is sequences, L is sites, and a is characters.
• Speed optimization: Uses heuristics to identify candidate joins, implements Neighbor-Joining algorithms, and applies nearest neighbor interchanges (NNIs), with FastTree 2 adding minimum-evolution subtree-pruning-regrafting (SPRs).
• Local bootstrapping: Estimates branch support via local bootstrapping to provide faster reliability assessment than full-distance-matrix bootstraps.
• CAT approximation: Employs the CAT approximation to estimate site-specific rates of evolution.

Scientific Applications:

• Large-scale phylogenetic inference: Infers phylogenies for large gene families and extensive sequence datasets.
• Ribosomal RNA analysis: Applied to rRNA datasets, e.g., computed phylogenies for 158,022 distinct 16S ribosomal RNAs in 17 hours using 2.4 GB of memory.
• Benchmarking and comparison: Demonstrated favorable performance in simulations and real-data comparisons against Neighbor-Joining, BIONJ, FastME, and PhyML 3.

Methodology:

Stores sequence profiles at internal nodes, implements Neighbor-Joining with heuristics to identify candidate joins, optimizes trees via nearest neighbor interchanges (NNIs), incorporates minimum-evolution subtree-pruning-regrafting (SPRs) in FastTree 2, applies the CAT approximation for site-specific rates, and assesses branch support with local bootstrapping.