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

As DNA sequencing accelerates, gene families are growing rapidly, but stan-dard methods for inferring phylogenies become computationally demanding for alignments of thousands of sequences. We present FastTree, a method for con-structing large phylogenies and for estimating their reliability. Instead of stor-ing 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 refines the topol-ogy with nearest-neighbor interchanges according to the minimum-evolution criterion. Compared to using a distance matrix, FastTree reduces the memory required from O(N2) to O(NLa + N N) and reduces the computation time from O(N2L) to O(N N log(N)La), where N is the number of sequences, L is the width of the alignment, and a is the size of the alphabet. To estimate the tree’s reliability, FastTree uses local bootstrapping, which gives another 100-fold speedup over distance matrix approaches. FastTree constructed trees, includ-ing support values, for biological alignments with 39,092 or 158,022 distinct sequences in less time than it takes to compute a distance matrix and in a frac-tion of the space. Traditional neighbor joining with 100 bootstraps would be 10,000 times slower and would require 50 gigabytes of memory. In simulations, FastTree is slightly more accurate than other minimum-evolution methods such as neighbor joining, BIONJ, or FastME, and on genuine alignments, FastTree produces topologies with higher likelihoods. FastTree is available a