Parallel algorithms for phylogenetic inference under a structured coalescent approximation

Abstract

Timely reconstruction of epidemic dynamics is essential for public health, and structured coalescent models constitute an essential tool for this purpose. However, statistical and computational challenges pose a critical barrier to their widespread use in analyzing large, outbreak-scale datasets. We overcome this limitation by introducing a scalable algorithmic framework with parallelization for a major structured coalescent approximation method, accelerating its performance by over an order of magnitude. This advance renders real-time phylogeographic inference practical for rapidly evolving viruses like avian influenza and dengue across dozens of regions, supporting more detailed and statistically rigorous insights for global pathogen surveillance.