FastTree 2--approximately maximum-likelihood trees for large alignments.

Price MN, Dehal PS, Arkin AP. · 2010

Read FastTree 2--approximately maximum-likelihood trees for large alignments. by Price MN, Dehal PS, Arkin AP. (2010) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc2835736.txt.

Introduction

Price, Dehal, and Arkin released FastTree 2 in 2010, a program that builds evolutionary trees from huge sets of aligned sequences. Tree building slows brutally as datasets grow, yet the largest gene families now hold hundreds of thousands of members. The update keeps the original speed while closing its accuracy gap.

New tree-shuffling moves and a per-site rate estimate sharpen the search. On test data the program edged out a standard likelihood tool. It also ran one hundred to one thousand times faster on large inputs, though the very slowest, most careful methods still beat it slightly. As a proof, it built a tree from nearly two hundred thirty-eight thousand ribosomal RNA sequences on a desktop in twenty-two hours.

Catalog record

CREATORPrice MN, Dehal PS, Arkin AP.
YEAR2010
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC2835736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments By Morgan N. Price, Paramvir S. Dehal, Adam P. Arkin, Art F. Y. Poon Published in: PLoS ONE DOI: 10.1371/journal.pone.0009490 ABSTRACT Background We recently described FastTree, a tool for inferring phylogenies for alignments with up to hundreds of thousands of sequences. Here, we describe improvements to FastTree that improve its accuracy without sacrificing scalability. Methodology/Principal Findings Where FastTree 1 used nearest-neighbor interchanges (NNIs) and the minimum-evolution criterion to improve the tree, FastTree 2 adds minimum-evolution subtree-pruning-regrafting (SPRs) and maximum-likelihood NNIs. FastTree 2 uses heuristics to restrict the search for better trees and estimates a rate of evolution for each site (the “CAT” approximation). Nevertheless, for both simulated and genuine alignments, FastTree 2 is slightly more accurate than a standard implementation of maximum-likelihood NNIs (PhyML 3 with default settings). Although FastTree 2 is not quite as accurate as methods that use maximum-likelihood SPRs, most of the splits that disagree are poorly supported, and for large alignments, FastTree 2 is 100–1,000 times faster. FastTree 2 inferred a topology and likelihood-based local support values for 237,882 distinct 16S ribosomal RNAs on a desktop computer in 22 hours and 5.8 gigabytes of memory. Conclusions/Significance FastTree 2 allows the inference of maximum-likelihood phylogenies for huge alignments. FastTree 2 is freely available at http://www.microbesonline.org/fasttree. INTRODUCTION Inferring evolutionary relationships, or phylogenies, from families of related DNA or protein sequences is a central method in computational biology. Sequence-based phylogenies are widely used to understand the evolutionary relationships of organisms and to analyze the functions of genes. The largest gene families already contain tens to hundreds of thousands of representatives, and with the rapid improvements in DNA sequencing, we expect even larger data sets to arrive soon. Large families can be aligned with profile-based methods that scale linearly with the number of sequences (http://hmmer.janelia.org/; [1]). However, most methods for inferring phylogenies from these alignments scale as O() or worse, where is the number of sequences and is the length (width) of the alignment. Thus, inferring phylogenies has become computationally challenging. We recently described a scalable method for inferring phylogenies, FastTree 1.0 [2]. FastTree 1.0 is based on the “minimum-evolution” principle – it tries to find a topology that minimizes the amount of evolution, or the sum of the branch lengths. FastTree 1.0 uses a heuristic variant of neighbor joining [3], [4] to quickly find a starting tree and uses nearest-neighbor interchanges (NNIs) to refine the topology. (A nearest-neighbor interchange swaps a node and its neighbor; for example, it might change ((A,B),C,D) to ((A,C),B,D) or ((A,D),B,C).) FastTree implements these operations in O() space, where is the number of characters in the alphabet, by storing profiles of subtrees instead of distances between them. This requires far less memory than storing the pairwise distances, which is necessary for neighbor joining and related approaches. This also allows for heuristics that reduce the theoretical running time to O(). (FastTree 1.0 also included some O() steps, but these have since been removed, see http://www.microbesonline.org/fasttree/ChangeLog.) In comparison, computing all pairwise distances, which is required with most minimum-evolution approaches, requires O() time. The main limitation of FastTree 1.0, as compared to other minimum-evolution methods, is that it does not correct distances for multiple substitutions during its initial neighbor joining phase. However, this is more than made up for by the NNIs. In practice, FastTree 1.0 is more accurate than most other minimum-evolution methods, but not as accurate as maximum-likelihood methods [2]. In the maximum-likelihood (ML) approach, evolution is explicitly modeled with a transition rate matrix, and the tree that best explains the data – the tree with the highest likelihood – is the best tree [5]. The ML criterion ranks the trees but does not specify how to find a good topology. Because ML phylogenetic inference is NP complete [6], no practical method can guarantee that it will find the optimal topology for a large alignment. The most scalable ML methods, such as PhyML and RAxML, begin with a starting tree produced by a faster method, and try to increase the likelihood by optimizing individual branch lengths and performing local rearrangements [7]–[9]. By re-optimizing only a few branch lengths at each move, the cost of considering or performing a move can be reduced to O() time, where is the size of the alphabet. However, in practice, the number of moves grows as roughly O(), and the optimization steps are inherently slow because they require numerical solving and iteration. This explains why both PhyML and RAxML can take over a day for just 1,000 protein sequences. Estimating the reliability of the tree with the bootstrap [10] generally increases the computational requirements another 100-fold (although this can be reduced by reusing computations across replicates [11]). Here, we describe FastTree 2, a tool for inferring ML trees for large alignments. Besides constructing an initial tree with neighbor joining and improving it with minimum-evolution NNIs, FastTree 2 uses minimum-evolution subtree-pruning-regrafting (SPRs) [8], [12] and ML NNIs to further improve the tree. (In subtree-pruning-regrafting, a subtree is removed from the tree and reinserted elsewhere, e.g., pruning and regrafting C might change ((A,B),(C,D),E) to ((A,(B,C)),D,E).) FastTree 2 uses heuristics to reduce the search space and hence to maintain the scalability of both stages. Another justification for reducing the search space is that intensive tree search often finds small improvements in the tree's length or likelihood, but these changes may not be statistically or biologically significant (e.g., [13]). Briefly, FastTree's key heuristics are: - It uses “linear SPRs” to consider just of the possible SPR moves. At each node, it examines the shortest SPRs first and then extends the most promising candidates. - It searches for SPR moves for every subtree just twice, instead of iterating until convergence. - During the ML phase, it limits the ML NNIs to at most rounds; in practice, it converges before it reaches this limit, but the limit ensures a predictable running time. - It limits the effort to optimize model parameters and branch lengths. - It abandons optimization for NNI moves that seem, after partial optimization, to significantly lower the likelihood. - It does not try to improve parts of the tree that did not improve in recent rounds. To account for the variation in rates across sites, FastTree uses the “CAT” approximation [14] rather than the standard discrete gamma model with four rates () [15]. Some sites evolve much more slowly than others, and the ideal way to account for this is to integrate the likelihood at each site over the (unknown) relative evolutionary rate of that site, using a prior distribution over the relative rates such as a gamma distribution. However, these integrals are analytically intractable and computationally prohibitive. The “” approach is to use four rate categories to approximate the continuous gamma distribution. However, still requires four times more CPU time and memory than a model with no rate variation across sites. Furthermore, for large alignments, the data tightly constrains the rate at each site. Thus, it is much faster, and just as accurate, to use a good estimate of the rate at each site (CAT) rather than to sum over four potential rates () [14]. FastTree selects the most likely rate for each site

Read the complete text