SCAMPP+FastTree: Improving Scalability for Likelihood-based Phylogenetic Placement

Phylogenetic placement is the problem of placing “query” sequences into an existing tree (called a “backbone tree”), and is useful in both microbiome analysis and to update large evolutionary trees. The most accurate phylogenetic placement method to date is the maximum likelihood-based method pplacer, which uses RAxML to estimate numeric parameters on the backbone tree and then adds the given query sequence to the edge that maximizes the probability that the resulting tree generates the query sequence. Unfortunately, pplacer fails to return valid outputs on many moderately large datasets, and so is limited to backbone trees with at most ∼10,000 leaves. In TCBB 2022, Wedell et al. introduced SCAMPP, a technique to enable pplacer to run on larger backbone trees. SCAMPP operates by finding a small “placement subtree” specific to each query sequence, within which the query sequence are placed using pplacer. That approach matched the scalability and accuracy of APPLES-2, the previous most scalable method. In this study, we explore a different aspect of pplacer’s strategy: the technique used to estimate numeric parameters on the backbone tree. We confirm anecdotal evidence that using FastTree instead of RAxML to estimate numeric parameters on the backbone tree enables pplacer to scale to much larger backbone trees, almost (but not quite) matching the scalability of APPLES-2 and pplacer-SCAMPP. We then evaluate the combination of these two techniques – SCAMPP and the use of FastTree. We show that this combined approach, pplacer-SCAMPP-FastTree, has the same scalability as APPLES-2, improves on the scalability of pplacer-FastTree, and achieves better accuracy than the comparably scalable methods. Availability: https://github.com/gillichu/PLUSplacer-taxtastic .