{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T14:38:44Z","timestamp":1782830324216,"version":"3.54.5"},"reference-count":48,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T00:00:00Z","timestamp":1705622400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01 AI153044"],"award-info":[{"award-number":["R01 AI153044"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01 AI162611"],"award-info":[{"award-number":["R01 AI162611"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Advancements in high-throughput genomic sequencing are delivering genomic pathogen data at an unprecedented rate, positioning statistical phylogenetics as a critical tool to monitor infectious diseases globally. This rapid growth spurs the need for efficient inference techniques, such as Hamiltonian Monte Carlo (HMC) in a Bayesian framework, to estimate parameters of these phylogenetic models where the dimensions of the parameters increase with the number of sequences N. HMC requires repeated calculation of the gradient of the data log-likelihood with respect to (wrt) all branch-length-specific (BLS) parameters that traditionally takes O(N2) operations using the standard pruning algorithm. A recent study proposes an approach to calculate this gradient in O(N), enabling researchers to take advantage of gradient-based samplers such as HMC. The CPU implementation of this approach makes the calculation of the gradient computationally tractable for nucleotide-based models but falls short in performance for larger state-space size models, such as Markov-modulated and codon models. Here, we describe novel massively parallel algorithms to calculate the gradient of the log-likelihood wrt all BLS parameters that take advantage of graphics processing units (GPUs) and result in many fold higher speedups over previous CPU implementations.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We benchmark these GPU algorithms on three computing systems using three evolutionary inference examples exploring complete genomes from 997 dengue viruses, 62 carnivore mitochondria and 49 yeasts, and observe a &amp;gt;128-fold speedup over the CPU implementation for codon-based models and &amp;gt;8-fold speedup for nucleotide-based models. As a practical demonstration, we also estimate the timing of the first introduction of West Nile virus into the continental Unites States under a codon model with a relaxed molecular clock from 104 full viral genomes, an inference task previously intractable.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>We provide an implementation of our GPU algorithms in BEAGLE v4.0.0 (https:\/\/github.com\/beagle-dev\/beagle-lib), an open-source library for statistical phylogenetics that enables parallel calculations on multi-core CPUs and GPUs. We employ a BEAGLE-implementation using the Bayesian phylogenetics framework BEAST (https:\/\/github.com\/beast-dev\/beast-mcmc).<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae030","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T08:51:56Z","timestamp":1705740716000},"source":"Crossref","is-referenced-by-count":8,"title":["Many-core algorithms for high-dimensional gradients on phylogenetic trees"],"prefix":"10.1093","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5027-3440","authenticated-orcid":false,"given":"Karthik","family":"Gangavarapu","sequence":"first","affiliation":[{"name":"Department of Biomathematics, David Geffen School of Medicine at UCLA, University of California, Los Angeles , Los Angeles, CA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiang","family":"Ji","sequence":"additional","affiliation":[{"name":"Department of Mathematics, School of Science & Engineering, Tulane University , New Orleans, LA, United States"}],"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, Rega Institute , KU Leuven, Leuven, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathieu","family":"Fourment","sequence":"additional","affiliation":[{"name":"Australian Institute for Microbiology and Infection, University of Technology Sydney , Ultimo, NSW, Australia"}],"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, Rega Institute , KU Leuven, Leuven, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0607-6025","authenticated-orcid":false,"suffix":"IV","given":"Frederick A","family":"Matsen","sequence":"additional","affiliation":[{"name":"Public Health Sciences Division, Fred Hutchinson Cancer Research Center , Seattle, WA, United States"},{"name":"Department of Statistics, University of Washington , Seattle, WA, United States"},{"name":"Department of Genome Sciences, University of Washington , Seattle, WA, United States"},{"name":"Howard Hughes Medical Institute, Fred Hutchinson Cancer Research Center , Seattle, WA, United States"}],"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 Biomathematics, David Geffen School of Medicine at UCLA, University of California, Los Angeles , Los Angeles, CA, United States"},{"name":"Department of Biostatistics, Jonathan and Karin Fielding School of Public Health, University of California, Los Angeles , Los Angeles, CA, United States"},{"name":"Department of Human Genetics, David Geffen School of Medicine at UCLA , Los Angeles, CA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2024,1,18]]},"reference":[{"key":"2024020317045253800_btae030-B1","author":"AMD","year":"2018"},{"key":"2024020317045253800_btae030-B2","author":"AMD","year":"2019"},{"key":"2024020317045253800_btae030-B3","doi-asserted-by":"crossref","first-page":"e2245","DOI":"10.1371\/journal.pntd.0002245","article-title":"Evolutionary dynamics of West Nile Virus in the United States, 1999\u20132011: phylogeny, selection pressure and evolutionary time-scale analysis","volume":"7","author":"A\u00f1ez","year":"2013","journal-title":"PLoS Negl Trop Dis"},{"key":"2024020317045253800_btae030-B4","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1093\/sysbio\/syz020","article-title":"BEAGLE 3: improved performance, scaling, and usability for a high-performance computing library for statistical phylogenetics","volume":"68","author":"Ayres","year":"2019","journal-title":"Syst Biol"},{"key":"2024020317045253800_btae030-B5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1093\/sysbio\/syaa037","article-title":"Markov-modulated continuous-time Markov chains to identify site- and branch-specific evolutionary variation in BEAST","volume":"70","author":"Baele","year":"2021","journal-title":"Syst Biol"},{"key":"2024020317045253800_btae030-B6","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1080\/10618600.2015.1035724","article-title":"Fast Hamiltonian Monte Carlo using GPU computing","volume":"25","author":"Beam","year":"2016","journal-title":"J Comput Graph Stat"},{"key":"2024020317045253800_btae030-B7","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1146\/annurev.micro.56.012302.160654","article-title":"The molecular biology of West Nile Virus: a new invader of the Western Hemisphere","volume":"56","author":"Brinton","year":"2002","journal-title":"Annu Rev Microbiol"},{"key":"2024020317045253800_btae030-B8","doi-asserted-by":"crossref","first-page":"7003","DOI":"10.1038\/s41467-022-33713-y","article-title":"Global disparities in sars-cov-2 genomic surveillance","volume":"13","author":"Brito","year":"2022","journal-title":"Nat Commun"},{"key":"2024020317045253800_btae030-B9","first-page":"33","author":"Bryant","year":"2005"},{"key":"2024020317045253800_btae030-B10","first-page":"845","article-title":"Outbreak of West Nile-like viral encephalitis\u2013New York, 1999","volume":"48","author":"Centers for Disease Control and Prevention (CDC)","year":"1999","journal-title":"MMWR Morb Mortal Wkly Rep"},{"key":"2024020317045253800_btae030-B11","author":"Chetlur","year":"2014"},{"key":"2024020317045253800_btae030-B12","volume-title":"CUDA Programming: A Developer\u2019s Guide to Parallel Computing with GPUs","author":"Cook","year":"2012","edition":"1st edn"},{"key":"2024020317045253800_btae030-B13","doi-asserted-by":"crossref","first-page":"e88","DOI":"10.1371\/journal.pbio.0040088","article-title":"Relaxed phylogenetics and dating with confidence","volume":"4","author":"Drummond","year":"2006","journal-title":"PLoS Biol"},{"key":"2024020317045253800_btae030-B14","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1093\/molbev\/msi103","article-title":"Bayesian coalescent inference of past population dynamics from molecular sequences","volume":"22","author":"Drummond","year":"2005","journal-title":"Mol Biol Evol"},{"key":"2024020317045253800_btae030-B15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1038\/nature22040","article-title":"Virus genomes reveal factors that spread and sustained the Ebola epidemic","volume":"544","author":"Dudas","year":"2017","journal-title":"Nature"},{"key":"2024020317045253800_btae030-B16","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Evolutionary trees from DNA sequences: a maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J Mol Evol"},{"key":"2024020317045253800_btae030-B17","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1093\/sysbio\/syaa056","article-title":"Relaxed random walks at scale","volume":"70","author":"Fisher","year":"2020","journal-title":"Syst Biol"},{"key":"2024020317045253800_btae030-B18","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1093\/sysbio\/syu084","article-title":"The phylogenetic likelihood library","volume":"64","author":"Flouri","year":"2015","journal-title":"Syst Biol"},{"key":"2024020317045253800_btae030-B19","doi-asserted-by":"crossref","first-page":"evad099","DOI":"10.1093\/gbe\/evad099","article-title":"Automatic differentiation is no panacea for phylogenetic gradient computation","volume":"15","author":"Fourment","year":"2023","journal-title":"Genome Biol Evol"},{"key":"2024020317045253800_btae030-B20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-10837-3_2","volume-title":"Numerical Optimization Techniques in Maximum Likelihood Tree Inference","author":"Guindon","year":"2019"},{"key":"2024020317045253800_btae030-B21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume":"57","author":"Hastings","year":"1970","journal-title":"Biometrika"},{"key":"2024020317045253800_btae030-B22","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1080\/10618600.2020.1754226","article-title":"Massive parallelization boosts big Bayesian multidimensional scaling","volume":"30","author":"Holbrook","year":"2021","journal-title":"J Comput Graph Stat"},{"key":"2024020317045253800_btae030-B23","doi-asserted-by":"crossref","first-page":"3047","DOI":"10.1093\/molbev\/msaa130","article-title":"Gradients do grow on trees: a linear-time o(n)-dimensional gradient for statistical phylogenetics","volume":"37","author":"Ji","year":"2020","journal-title":"Mol Biol Evol"},{"key":"2024020317045253800_btae030-B24","doi-asserted-by":"crossref","first-page":"e95722","DOI":"10.1371\/journal.pone.0095722","article-title":"The impact of modelling rate heterogeneity among sites on phylogenetic estimates of intraspecific evolutionary rates and timescales","volume":"9","author":"Jia","year":"2014","journal-title":"PLoS One"},{"key":"2024020317045253800_btae030-B25","doi-asserted-by":"crossref","first-page":"Article 14","DOI":"10.1515\/1544-6115.1779","article-title":"Hessian calculation for phylogenetic likelihood based on the pruning algorithm and its applications","volume":"11","author":"Kenney","year":"2012","journal-title":"Stat Appl Genet Mol Biol"},{"key":"2024020317045253800_btae030-B26","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02109483","article-title":"Maximum likelihood inference of protein phylogeny and the origin of chloroplasts","volume":"31","author":"Kishino","year":"1990","journal-title":"J Mol Evol"},{"key":"2024020317045253800_btae030-B27","doi-asserted-by":"crossref","first-page":"2333","DOI":"10.1126\/science.286.5448.2333","article-title":"Origin of the West Nile virus responsible for an outbreak of encephalitis in the northeastern United States","volume":"286","author":"Lanciotti","year":"1999","journal-title":"Science"},{"key":"2024020317045253800_btae030-B28","doi-asserted-by":"crossref","first-page":"5110","DOI":"10.1038\/s41467-020-18877-9","article-title":"Accommodating individual travel history and unsampled diversity in Bayesian phylogeographic inference of SARS-CoV-2","volume":"11","author":"Lemey","year":"2020","journal-title":"Nat Commun"},{"key":"2024020317045253800_btae030-B29","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J Chem Phys"},{"key":"2024020317045253800_btae030-B30","author":"Mitchell"},{"key":"2024020317045253800_btae030-B31","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1201\/b10905-6","article-title":"MCMC using Hamiltonian dynamics","volume":"2","author":"Neal","year":"2011","journal-title":"Handbook Markov Chain Monte Carlo"},{"key":"2024020317045253800_btae030-B32","doi-asserted-by":"crossref","first-page":"1518","DOI":"10.1038\/s41591-021-01472-w","article-title":"The next phase of sars-cov-2 surveillance: real-time molecular epidemiology","volume":"27","author":"Oude Munnink","year":"2021","journal-title":"Nat Med"},{"key":"2024020317045253800_btae030-B33","doi-asserted-by":"crossref","first-page":"15066","DOI":"10.1073\/pnas.1206598109","article-title":"Unifying the spatial epidemiology and molecular evolution of emerging epidemics","volume":"109","author":"Pybus","year":"2012","journal-title":"Proc Natl Acad Sci USA"},{"key":"2024020317045253800_btae030-B34","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1093\/sysbio\/syy032","article-title":"Posterior summarization in Bayesian phylogenetics using Tracer 1.7","volume":"67","author":"Rambaut","year":"2018","journal-title":"Syst Biol"},{"key":"2024020317045253800_btae030-B35","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.3201\/eid1008.040077","article-title":"West Nile virus in California","volume":"10","author":"Reisen","year":"2004","journal-title":"Emerg Infect Dis"},{"key":"2024020317045253800_btae030-B36","doi-asserted-by":"crossref","first-page":"628","DOI":"10.15585\/mmwr.mm7118a3","article-title":"West Nile virus and other domestic nationally notifiable arboviral diseases\u2014United States, 2020","volume":"71","author":"Soto","year":"2022","journal-title":"MMWR Morb Mortal Wkly Rep"},{"key":"2024020317045253800_btae030-B37","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/bioinformatics\/btu033","article-title":"RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies","volume":"30","author":"Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"2024020317045253800_btae030-B38","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/MCSE.2010.69","article-title":"OpenCL: a parallel programming standard for heterogeneous computing systems","volume":"12","author":"Stone","year":"2010","journal-title":"Comput Sci Eng"},{"key":"2024020317045253800_btae030-B39","doi-asserted-by":"crossref","first-page":"vey016","DOI":"10.1093\/ve\/vey016","article-title":"Bayesian phylogenetic and phylodynamic data integration using BEAST 1.10","volume":"4","author":"Suchard","year":"2018","journal-title":"Virus Evol"},{"key":"2024020317045253800_btae030-B40","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1093\/bioinformatics\/btp244","article-title":"Many-core algorithms for statistical phylogenetics","volume":"25","author":"Suchard","year":"2009","journal-title":"Bioinformatics"},{"key":"2024020317045253800_btae030-B41","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1198\/jcgs.2010.10016","article-title":"Understanding GPU programming for statistical computation: studies in massively parallel massive mixtures","volume":"19","author":"Suchard","year":"2010","journal-title":"J Comput Graph Stat"},{"key":"2024020317045253800_btae030-B42","first-page":"57","article-title":"Lectures on mathematics in the life sciences","volume":"17","author":"Tavar\u00e9","year":"1986","journal-title":"Am Math Soc"},{"key":"2024020317045253800_btae030-B43","first-page":"1","article-title":"Massive parallelization of massive Sample-Size survival analysis","volume":"00","author":"Yang","year":"2023","journal-title":"J Comput Graph Stat"},{"key":"2024020317045253800_btae030-B44","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/BF00160154","article-title":"Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites: approximate methods","volume":"39","author":"Yang","year":"1994","journal-title":"J Mol Evol"},{"key":"2024020317045253800_btae030-B45","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0169-5347(96)10041-0","article-title":"Among-site rate variation and its impact on phylogenetic analyses","volume":"11","author":"Yang","year":"1996","journal-title":"Trends Ecol Evol"},{"key":"2024020317045253800_btae030-B46","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1093\/genetics\/155.1.431","article-title":"Codon-substitution models for heterogeneous selection pressure at amino acid sites","volume":"155","author":"Yang","year":"2000","journal-title":"Genetics"},{"key":"2024020317045253800_btae030-B47","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1214\/10-STS336","article-title":"Graphics processing units and high-dimensional optimization","volume":"25","author":"Zhou","year":"2010","journal-title":"Stat Sci"},{"key":"2024020317045253800_btae030-B48","author":"Zwickl","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae030\/56254401\/btae030.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/2\/btae030\/56576653\/btae030.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/2\/btae030\/56576653\/btae030.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T17:05:24Z","timestamp":1706979924000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae030\/7577857"}},"subtitle":[],"editor":[{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,1,18]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae030","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,2,1]]},"published":{"date-parts":[[2024,1,18]]},"article-number":"btae030"}}