Online tree expansion could help solve the problem of scalability in Bayesian phylogenetics

Jakub Truszkowski, Allison Perrigo, David Broman, Fredrik Ronquist, Alexandre AntonelliSystematic 2023 · DOI

TL;DR

Bayesian phylogenetics, while powerful, struggles with the computational demands of ever-growing genomic datasets. This paper explores "online phylogenetics" and Sequential Monte Carlo (SMC) methods as promising solutions to efficiently update phylogenetic trees with new data, potentially speeding up inference by orders of magnitude.

What Problem Does This Paper Address?

Phylogenetic inference aims to reconstruct the evolutionary history of life, often represented as a tree. Bayesian methods are highly valued for their ability to quantify uncertainty and incorporate complex evolutionary models. However, these methods are computationally intensive, typically limiting their application to datasets with only a few hundred sequences. This is a major bottleneck in the era of genomics, where datasets can contain thousands or even millions of sequences. Researchers are often forced to use faster, but less accurate, methods like maximum parsimony or maximum likelihood. The challenge is to make powerful Bayesian methods scalable to handle these massive, and continually growing, datasets without sacrificing accuracy.

Methods

The paper discusses two main approaches to address the scalability problem:

  • Online Phylogenetics: This paradigm focuses on updating existing phylogenetic analyses with new sequence data, rather than recomputing everything from scratch. This is particularly relevant when researchers want to add a few new species to a large, well-studied dataset. Methods discussed include:
  • Phylogenetic Placement: Algorithms like EPA and EPA-ng that efficiently find the best placement for a new sequence on an existing reference tree.
  • Online MCMC: Adapting Markov Chain Monte Carlo (MCMC) methods to incorporate new sequences. This involves starting with a tree from a previous MCMC run and then performing MCMC iterations on the updated tree.
  • Online Sequential Monte Carlo (SMC): SMC methods maintain a "population" of possible trees (particles) and update them as new data arrives. This approach is naturally suited for online updates and can be significantly faster than traditional MCMC.
  • Alternatives to MCMC: The paper highlights Sequential Monte Carlo (SMC) as a key alternative to MCMC for scalable Bayesian inference. SMC offers potential advantages in speed and convergence, especially for online applications.

The authors also identify five specific challenges that need to be overcome for these methods to reach their full potential: path degeneracy in SMC, balancing local vs. global tree modifications, memory usage and parallelization, combining MCMC and SMC, and software implementation.

Datasets

The paper discusses the application of these methods to real-world datasets, specifically mentioning:

  • SARS-CoV-2 genomes: The rapid sequencing of SARS-CoV-2 genomes during the COVID-19 pandemic is cited as a prime example where fast phylogenetic methods are crucial. The paper mentions analyses involving up to 1000s of genomes.
  • Simulated data: Experiments on simulated data are used to evaluate the performance and accuracy of online SMC methods.

The paper does not introduce new benchmark datasets but rather discusses how existing datasets, particularly those that are rapidly growing, motivate the need for these new methods.

Key Insights and Ideas

  • The "online" paradigm is a game-changer: Instead of re-running massive analyses from scratch every time new data emerges, updating existing analyses offers a significant computational shortcut. This is especially relevant in fields like phylodynamics where data is constantly being generated.
  • SMC offers a compelling alternative to MCMC: While MCMC is the workhorse of Bayesian phylogenetics, its slow convergence for large datasets is a major limitation. SMC, with its population-based approach, shows promise for faster and more scalable inference, particularly in an online setting.
  • There's a trade-off between local and global updates: Online methods often focus on local modifications to the tree when adding new sequences. The paper raises the question of whether these local updates are sufficient for accurate inference, especially when considering global model parameters or when dealing with complex evolutionary signals.
  • Software implementation is a critical bottleneck: Even with promising algorithms, the lack of user-friendly and efficient software implementations can hinder widespread adoption. The authors suggest probabilistic programming languages (PPLs) as a potential solution for automating and streamlining the development of these complex algorithms.

Key Results

The paper doesn't present a single set of quantitative results but rather surveys existing approaches and discusses their potential. However, it highlights:

  • Potential for orders of magnitude speedup: The authors believe that online phylogenetic approaches and SMC could potentially speed up tree inference by orders of magnitude compared to traditional offline methods.
  • Comparable accuracy: For some applications, online methods have shown accuracy comparable to traditional methods, especially when dealing with densely sampled datasets.
  • Efficiency gains demonstrated: Studies on SARS-CoV-2 data and simulated datasets have shown significant improvements in computational efficiency with online methods.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Convergence diagnostics for online MCMC: It's not always clear how to monitor the convergence of online MCMC approaches, making rigorous performance comparisons challenging.
  • Path degeneracy in SMC: A significant limitation of current online SMC methods is the accumulation of resampling error, which limits the number of sequences that can be added. Future work should explore remedies like MCMC rejuvenation or rejection control.
  • Global parameter updates: The impact of local updates on global phylogenetic inference needs further investigation.
  • Memory management and parallelization: Developing online algorithms that efficiently manage memory and leverage parallel architectures (like GPUs) is crucial for handling massive datasets.
  • Combining MCMC and SMC: Exploring synergies between MCMC and SMC methods could lead to more powerful and efficient inference tools.
  • Software development: Continued development of user-friendly software, potentially leveraging PPLs, is essential for broader adoption.

The paper concludes with a call for collaborative efforts to accelerate the development of these methods for real-time tree expansion.

Summary updated

Abstract

Bayesian phylogenetics is now facing a critical point. Over the last 20 years, Bayesian methods have reshaped phylogenetic inference and gained widespread popularity due to their high accuracy, the ability to quantify the uncertainty of inferences and the possibility of accommodating multiple aspects of evolutionary processes in the models that are used. Unfortunately, Bayesian methods are computationally expensive, and typical applications involve at most a few hundred sequences. This is problematic in the age of rapidly expanding genomic data and increasing scope of evolutionary analyses, forcing researchers to resort to less accurate but faster methods, such as maximum parsimony and maximum likelihood. Does this spell doom for Bayesian methods? Not necessarily. Here, we discuss some recently proposed approaches that could help scale up Bayesian analyses of evolutionary problems considerably. We focus on two particular aspects: online phylogenetics, where new data sequences are added to existing analyses, and alternatives to Markov chain Monte Carlo (MCMC) for scalable Bayesian inference. We identify 5 specific challenges and discuss how they might be overcome. We believe that online phylogenetic approaches and Sequential Monte Carlo hold great promise and could potentially speed up tree inference by orders of magnitude. We call for collaborative efforts to speed up the development of methods for real-time tree expansion through online phylogenetics.
BibTeX
@inproceedings{truszkowski2023online,
  author = {Jakub Truszkowski and Allison Perrigo and David Broman and Fredrik Ronquist and Alexandre Antonelli},
  title = {{Online tree expansion could help solve the problem of scalability in Bayesian phylogenetics}},
  booktitle = {Systematic},
  year = {2023},
  doi = {10.1093/sysbio/syad045},
}
Figure