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

Abstract

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 (VO_SCPLOWINEC_SCPLOW), 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. VO_SCPLOWINEC_SCPLOW 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 VO_SCPLOWINEC_SCPLOW can effectively approximate the results of the best available Bayesian methods with speeds orders of magnitude faster. We then apply VO_SCPLOWINEC_SCPLOW 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.