FastTree: computing large minimum evolution trees with profiles instead of a distance matrix.

Area of Science:

• Computational Biology
• Bioinformatics
• Phylogenetics

Background:

• Gene families are expanding rapidly, posing scalability challenges for traditional phylogenetic inference methods.
• Standard phylogenetic methods struggle with sequence alignments exceeding 10,000 sequences.

Purpose of the Study:

• To present FastTree, a new method for constructing large phylogenies and estimating their reliability.
• To overcome the computational limitations of existing phylogenetic inference techniques for large datasets.

Main Methods:

• FastTree stores sequence profiles of internal nodes instead of distance matrices.
• It employs Neighbor-Joining with heuristics for rapid join identification and nearest neighbor interchanges for tree length reduction.
• Local bootstrapping is utilized for efficient reliability estimation.

Main Results:

• FastTree requires significantly less memory (O(NLa + N)) and time (O(N log (N)La)) compared to distance matrix methods (O(N(2)) space, O(N(2)L) time).
• It achieved a 100-fold speedup in reliability estimation via local bootstrapping.
• FastTree successfully computed a tree for 158,022 16S ribosomal RNAs in 17 hours using 2.4 GB of memory.

Conclusions:

• FastTree provides a scalable and efficient solution for large-scale phylogenetic analysis.
• The method demonstrates improved accuracy and likelihoods compared to existing algorithms.
• FastTree is a valuable tool for researchers dealing with rapidly growing gene families and large sequence datasets.