VINE: Variational inference for scalable Bayesian reconstruction of species and cell-lineage phylogenies.

Bayesian methods are now widely used in reconstructing both species and cell-lineage phylogenies, but they remain heavily reliant on computationally intensive Markov chain Monte Carlo sampling. Phylogenetic variational inference (VI) circumvents this dependency but so far has been limited in speed and scalability. Here we introduce Variational Inference with Node Embeddings (Vine), a computational method that combines an embedding of taxa in a high-dimensional space and a distance-based "decoder" with several algorithmic innovations to dramatically improve phylogenetic VI. Vine supports both standard DNA substitution models and CRISPR barcode-mutation models for inference of cell-lineage trees and tissue-migration histories. In extensive simulation experiments, we show that Vine is comparable in accuracy to the best available Bayesian methods with speeds orders of magnitude faster. We then apply Vine to ~1,000 complete SARS-CoV-2 genomes and ~900 lung-cancer cell barcodes, showing reductions in compute time from days to hours or minutes.