Fast and Accurate Branch Support Calculation for Distance-Based Phylogenetic Placements

Placing a new sequence onto an existing phylogenetic tree is increasingly used in downstream applications ranging from microbiome analyses to epidemic tracking. Most such applications deal with noisy data, incomplete references, and model misspecifications, all of which make the correct placement uncertain. While recent placement methods have increasingly enabled placement on ultra-large backbone trees with tens to hundreds of thousands of species, they have mostly ignored the issue of uncertainty. Here, we build on the recently developed distance-based phylogenetic placement methodology and show how the distribution of placements can be estimated per input sequence. We compare parametric and non-parametric sampling methods, showing that non-parametric bootstrapping is far more accurate in estimating uncertainty. Finally, we design and implement a linear algebraic implementation of bootstrapping that makes it faster, and we incorporate the computation of support values as a new feature in the APPLES software.

Automated summary

Placing a new sequence onto an existing phylogenetic tree is important for various downstream applications. Existing methods often ignore the issue of uncertainty, but we have successfully estimated the distribution of placements using a distance-based approach and found that non-parametric bootstrapping is more accurate in estimating uncertainty.