Parallel algorithms for phylogenetic inference under a structured coalescent approximation
Proceedings of the National Academy of Sciences · 05.05.2026 · 123 (18)
DOI: 10.1073/pnas.2602412123 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the National Academy of Sciences, online erschienen am 28.04.2026. Verfasst von Yucai Shao und 6 weiteren Autor:innen. Beteiligte Einrichtung: Department of Biostatistics, Jonathan and Karin Fielding School of Public Health, University of California, Los Angeles, CA 90095. Hauptthemen laut MEDLINE: Phylogeny, Algorithms. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: HHS | NIH | National Institute of Allergy and Infectious Diseases (NIAID), Wellcome Trust (WT), EC | European Research Council (ERC).
Abstract (Originalsprache)
Advances in molecular epidemiology and computational modeling have improved our ability to track pathogen evolution, but accurate reconstruction of spatiotemporal transmission remains essential for epidemic preparedness and response. Structured coalescent models offer a phylogeographic framework by restricting coalescence to lineages within the same deme. Although the Bayesian structured coalescent approximation (BASTA) provides a tractable approach, contemporary phylogeographic analyses involving dozens of localities and hundreds to thousands of genomes exceed the computational capacity of existing implementations. The BASTA likelihood scales cubically with deme count and quadratically with sequence count due to matrix exponentiation and partial likelihood vectors update. Here, we introduce an algorithmic restructuring of the structured coalescent likelihood that eliminates redundancies, optimizes memory access, and exposes parallelization opportunities. Our approach reorganizes computations along three dimensions: i) independent calculation of deme-transition probability matrices across time intervals; ii) simultaneous evaluation of partial likelihood vectors within temporal slices; and iii) concurrent aggregation of coalescent probabilities. Algorithmic restructuring cuts average coalescent likelihood computation by 7 to 8 fold, and parallelization further boosts performance to 10 to 26 fold, enabling joint phylogeographic analyses of dengue virus across 10 South American countries and H5N1 avian influenza across 20 Eurasian regions to finish in a fraction of prior time. This computational efficiency also enables comparison between backward-in-time structured coalescent approximations and forward-in-time phylogeographic methods, revealing that the former provides appropriately conservative posterior estimates, particularly at intermediate phylogenetic depths. We integrate our implementation into the BEAST X and BEAGLE software packages, providing researchers with an accessible and scalable tool for real-time phylogeographic surveillance of rapidly evolving pathogens.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Department of Biostatistics, Jonathan and Karin Fielding School of Public Health, University of California, Los Angeles, CA 90095.
- Department of Biomathematics, David Geffen School of Medicine at UCLA, University of California Los Angeles, Los Angeles, CA 90095.
- Department of Human Genetics, David Geffen School of Medicine at UCLA, University of California, Los Angeles, CA 90095.
- School of Biological Sciences, Institute of Ecology and Evolution, University of Edinburgh, Edinburgh EH9 2FL, United Kingdom.
- Department of Statistics, College of Liberal Arts and Sciences, Iowa State University, Ames, IA 50011.
- Department of Microbiology, Immunology and Transplantation, Rega Institute, Katholieke Universiteit Leuven, Leuven 3000, Belgium.
ORCID-Profile: Yucai Shao, Marc A Suchard, Philippe Lemey, Guy Baele
Förderung
- HHS | NIH | National Institute of Allergy and Infectious Diseases (NIAID)
- Wellcome Trust (WT)
- EC | European Research Council (ERC)
- Fonds Wetenschappelijk Onderzoek (FWO)
- European Union
Zitieren
APA
Shao, Y., Suchard, M. A., Rambaut, A., Ji, X., Lemey, P., Vasylyeva, T. I., & Baele, G. (2026). Parallel algorithms for phylogenetic inference under a structured coalescent approximation. Proceedings of the National Academy of Sciences, 123(18). https://doi.org/10.1073/pnas.2602412123
Vancouver
Shao Y, Suchard MA, Rambaut A, Ji X, Lemey P, Vasylyeva TI, et al. Parallel algorithms for phylogenetic inference under a structured coalescent approximation. Proceedings of the National Academy of Sciences. 2026;123(18). doi:10.1073/pnas.2602412123
BibTeX
@article{Shao2026,
author = {Shao, Yucai and Suchard, Marc A and Rambaut, Andrew and Ji, Xiang and Lemey, Philippe and Vasylyeva, Tetyana I and Baele, Guy},
title = {Parallel algorithms for phylogenetic inference under a structured coalescent approximation},
journal = {Proceedings of the National Academy of Sciences},
year = {2026},
volume = {123},
number = {18},
doi = {10.1073/pnas.2602412123}
}
EUVIMED