{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T22:29:33Z","timestamp":1787005773351,"version":"build-2736575974"},"reference-count":46,"publisher":"National Academy of Sciences","issue":"18","license":[{"start":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T00:00:00Z","timestamp":1777334400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000060","name":"HHS | NIH | National Institute of Allergy and Infectious Diseases","doi-asserted-by":"publisher","award":["R01 AI153044 R01 AI162611"],"award-info":[{"award-number":["R01 AI153044 R01 AI162611"]}],"id":[{"id":"10.13039\/100000060","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010269","name":"Wellcome Trust","doi-asserted-by":"publisher","award":["206298\/Z\/17\/Z"],"award-info":[{"award-number":["206298\/Z\/17\/Z"]}],"id":[{"id":"10.13039\/100010269","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"EC | European Research Council","doi-asserted-by":"publisher","award":["no. 725422"],"award-info":[{"award-number":["no. 725422"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["G005323N G051322N"],"award-info":[{"award-number":["G005323N G051322N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["G0E1420N G098321N"],"award-info":[{"award-number":["G0E1420N G098321N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["no. 101094685 no. 101102733"],"award-info":[{"award-number":["no. 101094685 no. 101102733"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2026,5,5]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1073\/pnas.2602412123","type":"journal-article","created":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T17:59:57Z","timestamp":1777399197000},"update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":1,"title":["Parallel algorithms for phylogenetic inference under a structured coalescent approximation"],"prefix":"10.1073","volume":"123","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-8703-7651","authenticated-orcid":false,"given":"Yucai","family":"Shao","sequence":"first","affiliation":[{"name":"Department of Biostatistics","place":["Los Angeles"]},{"name":"Jonathan and Karin Fielding School of Public Health","place":["Los Angeles"]},{"name":"University of California","place":["Los Angeles"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9818-479X","authenticated-orcid":false,"given":"Marc A.","family":"Suchard","sequence":"additional","affiliation":[{"name":"Department of Biostatistics","place":["Los Angeles"]},{"name":"Jonathan and Karin Fielding School of Public Health","place":["Los Angeles"]},{"name":"University of California","place":["Los Angeles"]},{"name":"Department of Biomathematics","place":["Los Angeles"]},{"name":"David Geffen School of Medicine at UCLA","place":["Los Angeles"]},{"name":"University of California Los Angeles","place":["Los Angeles"]},{"name":"Department of Human Genetics","place":["Los Angeles"]},{"name":"David Geffen School of Medicine at UCLA","place":["Los Angeles"]},{"name":"University of California","place":["Los Angeles"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Rambaut","sequence":"additional","affiliation":[{"name":"School of Biological Sciences, Institute of Ecology and Evolution","place":["Edinburgh, United Kingdom"]},{"name":"University of Edinburgh","place":["Edinburgh, United Kingdom"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiang","family":"Ji","sequence":"additional","affiliation":[{"name":"Department of Statistics","place":["Ames"]},{"name":"College of Liberal Arts and Sciences","place":["Ames"]},{"name":"Iowa State University","place":["Ames"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2826-5353","authenticated-orcid":false,"given":"Philippe","family":"Lemey","sequence":"additional","affiliation":[{"name":"Department of Microbiology, Immunology and Transplantation","place":["Leuven, Belgium"]},{"name":"Rega Institute, Katholieke Universiteit Leuven","place":["Leuven, Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tetyana I.","family":"Vasylyeva","sequence":"additional","affiliation":[{"name":"Department of Population Health and Disease Prevention","place":["Irvine"]},{"name":"University of California","place":["Irvine"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1915-7732","authenticated-orcid":false,"given":"Guy","family":"Baele","sequence":"additional","affiliation":[{"name":"Department of Microbiology, Immunology and Transplantation","place":["Leuven, Belgium"]},{"name":"Rega Institute, Katholieke Universiteit Leuven","place":["Leuven, Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2026,4,28]]},"reference":[{"key":"e_1_3_4_1_2","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/146.4.1501"},{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ge.29.120195.002153"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00173909"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/159.2.893"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000520"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.ppat.1000918"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.3390\/d15010088"},{"key":"e_1_3_4_8_2","first-page":"44","article-title":"Gene genealogies and the coalescent process","volume":"7","author":"Hudson R. R.","year":"1990","unstructured":"R. R. Hudson , Gene genealogies and the coalescent process. Oxf. Surv. Evol. Biol. 7, 44 (1990).","journal-title":"Oxf. Surv. Evol. Biol."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu201"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1534\/genetics.113.150904"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msx186"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty406"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pgen.1005421"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/ve\/vead010"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp244"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx088"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae030"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-025-02751-x"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syz020"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S00361445024180"},{"key":"e_1_3_4_22_2","first-page":"483","article-title":"Validity of the single processor approach to achieving large-scale computing capabilities","volume":"30","author":"Amdahl G. M.","year":"1967","unstructured":"G. M. Amdahl, Validity of the single processor approach to achieving large-scale computing capabilities. AFIPS Conf. Proc. 30, 483\u2013485 (1967).","journal-title":"AFIPS Conf. Proc."},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/gbe\/evx236"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2019.07.018"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msab364"},{"key":"e_1_3_4_26_2","first-page":"1701","article-title":"Markov chains for exploring posterior distributions","volume":"22","author":"Tierney L.","year":"1994","unstructured":"L. Tierney, Markov chains for exploring posterior distributions. Ann. Stat. 22, 1701\u20131728 (1994).","journal-title":"Ann. Stat."},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pntd.0002769"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cub.2011.05.058"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101694"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00160154"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.0040088"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/cjs.5550360302"},{"key":"e_1_3_4_33_2","first-page":"20141324","article-title":"Simultaneous reconstruction of evolutionary history and epidemiological dynamics from viral sequences with the birth-death SIR model","volume":"12","author":"De Maio N.","year":"2015","unstructured":"N. De Maio, C. H. Wu, K. M. O\u2019Reilly, D. Wilson, Simultaneous reconstruction of evolutionary history and epidemiological dynamics from viral sequences with the birth-death SIR model. J. R. Soc. Interface 12, 20141324 (2015).","journal-title":"J. R. Soc. Interface"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syy032"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaf488"},{"key":"e_1_3_4_36_2","first-page":"453","article-title":"An invariant form for the prior probability in estimation problems","volume":"186","author":"Jeffreys H.","year":"1946","unstructured":"H. Jeffreys, An invariant form for the prior probability in estimation problems. Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci. 186, 453\u2013461 (1946).","journal-title":"Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci."},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/viro.1998.9488"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msaa047"},{"key":"e_1_3_4_39_2","unstructured":"M. Betancourt A conceptual introduction to Hamiltonian Monte Carlo. arXiv [Preprint] (2017). https:\/\/doi.org\/10.48550\/arXiv.1701.02434 (Accessed 28 September 2025)."},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.ppat.1003932"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1013421"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msn090"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/mss265"},{"key":"e_1_3_4_44_2","doi-asserted-by":"crossref","unstructured":"Y. Shao Supplementary archive for: Parallel algorithms for phylogenetic inference under a structured coalescent approximation. GitHub. https:\/\/github.com\/suchard-group\/structured_coalescent_cpu_supplement. Accessed 28 September 2025.","DOI":"10.1101\/2025.09.22.677844"},{"key":"e_1_3_4_45_2","unstructured":"D. L. Ayres BEAGLE library basta branch. GitHub. https:\/\/github.com\/beagle-dev\/beagle-lib\/tree\/basta. Accessed 28 September 2025."},{"key":"e_1_3_4_46_2","unstructured":"G. Baele BEAST MCMC BigFastTreeModel branch. GitHub. https:\/\/github.com\/beast-dev\/beast-mcmc\/tree\/BigFastTreeModel. Accessed 28 September 2025."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.2602412123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:01:21Z","timestamp":1777399281000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/10.1073\/pnas.2602412123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,28]]},"references-count":46,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2026,5,5]]}},"alternative-id":["10.1073\/pnas.2602412123"],"URL":"https:\/\/doi.org\/10.1073\/pnas.2602412123","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2025.09.22.677844","asserted-by":"object"}]},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,28]]},"assertion":[{"value":"2026-01-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e2602412123"}}