{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T03:35:57Z","timestamp":1792985757038,"version":"4.5.0"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Motivation: Statistical phylogenetics is computationally intensive, resulting in considerable attention meted on techniques for parallelization. Codon-based models allow for independent rates of synonymous and replacement substitutions and have the potential to more adequately model the process of protein-coding sequence evolution with a resulting increase in phylogenetic accuracy. Unfortunately, due to the high number of codon states, computational burden has largely thwarted phylogenetic reconstruction under codon models, particularly at the genomic-scale. Here, we describe novel algorithms and methods for evaluating phylogenies under arbitrary molecular evolutionary models on graphics processing units (GPUs), making use of the large number of processing cores to efficiently parallelize calculations even for large state-size models.<\/jats:p>\n                  <jats:p>Results: We implement the approach in an existing Bayesian framework and apply the algorithms to estimating the phylogeny of 62 complete mitochondrial genomes of carnivores under a 60-state codon model. We see a near 90-fold speed increase over an optimized CPU-based computation and a &amp;gt;140-fold increase over the currently available implementation, making this the first practical use of codon models for phylogenetic inference over whole mitochondrial or microorganism genomes.<\/jats:p>\n                  <jats:p>Availability and implementation: Source code provided in BEAGLE: Broad-platform Evolutionary Analysis General Likelihood Evaluator, a cross-platform\/processor library for phylogenetic likelihood computation (http:\/\/beagle-lib.googlecode.com\/). We employ a BEAGLE-implementation using the Bayesian phylogenetics framework BEAST (http:\/\/beast.bio.ed.ac.uk\/).<\/jats:p>\n                  <jats:p>Contact: \u00a0msuchard@ucla.edu; a.rambaut@ed.ac.uk<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp244","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T21:28:58Z","timestamp":1239830938000},"page":"1370-1376","source":"Crossref","is-referenced-by-count":382,"title":["Many-core algorithms for statistical phylogenetics"],"prefix":"10.1093","volume":"25","author":[{"given":"Marc A.","family":"Suchard","sequence":"first","affiliation":[{"name":"1 Department of Biomathematics, 2Department of Biostatistics, 3Department of Human Genetics, University of California, Los Angeles, CA 90095, USA and 4Institute of Evolutionary Biology, University of Edinburgh, Edinburgh, EH9 3JT, UK"},{"name":"1 Department of Biomathematics, 2Department of Biostatistics, 3Department of Human Genetics, University of California, Los Angeles, CA 90095, USA and 4Institute of Evolutionary Biology, University of Edinburgh, Edinburgh, EH9 3JT, UK"},{"name":"1 Department of Biomathematics, 2Department of Biostatistics, 3Department of Human Genetics, University of California, Los Angeles, CA 90095, USA and 4Institute of Evolutionary Biology, University of Edinburgh, Edinburgh, EH9 3JT, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Rambaut","sequence":"additional","affiliation":[{"name":"1 Department of Biomathematics, 2Department of Biostatistics, 3Department of Human Genetics, University of California, Los Angeles, CA 90095, USA and 4Institute of Evolutionary Biology, University of Edinburgh, Edinburgh, EH9 3JT, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2009,4,15]]},"reference":[{"key":"2023013111551721900_B1","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bioinformatics\/btg427","article-title":"Parallel metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference","volume":"20","author":"Altekar","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013111551721900_B2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1017\/S0006323199005307","article-title":"Building large trees by combining phylogenetic information: a complete phylogeny of the extant Carnivora (Mammalia)","volume":"74","author":"Bininda-Emonds","year":"1999","journal-title":"Biol. Rev."},{"key":"2023013111551721900_B3","first-page":"415","article-title":"Initial experiences porting a bioinformatics application to a graphics processor","volume-title":"Proceedings of 10th Panhellenic Conference on Informatics (PCI2005).","author":"Charalambous","year":"2005"},{"key":"2023013111551721900_B4","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1002\/cpe.4330060702","article-title":"PUMMA: parallel universal matrix multiplication algorithms on distributed memory concurrent computers","volume":"6","author":"Choi","year":"1994","journal-title":"Concurrency Pract. Exp."},{"key":"2023013111551721900_B5","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.ympev.2005.04.025","article-title":"A phylogeny of the Caniformia (order Carnivora) based on 12 complete protein-coding mitochondrial genes","volume":"37","author":"Delisle","year":"2005","journal-title":"Mol. Phylogenet. Evol."},{"key":"2023013111551721900_B6","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":"2023013111551721900_B7","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":"2023013111551721900_B8","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/S0743-7315(03)00079-0","article-title":"Parallel algorithms for Bayesian phylogenetic inference","volume":"63","author":"Feng","year":"2003","journal-title":"J. Parallel Distr. Comput."},{"key":"2023013111551721900_B9","doi-asserted-by":"crossref","DOI":"10.1109\/IPDPS.2007.370214","article-title":"Building the Tree of Life on terascale systems","volume-title":"Parallel and Distributed Processing Symposium (IPDPS 2007).","author":"Feng","year":"2007"},{"key":"2023013111551721900_B10","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1006\/mpev.2000.0819","article-title":"Whence the red panda?","volume":"17","author":"Flynn","year":"2000","journal-title":"Mol. Phylogenet. Evol."},{"key":"2023013111551721900_B11","first-page":"725","article-title":"A codon-based model of nucleotide substitution for protein-coding DNA sequences","volume":"11","author":"Goldman","year":"1994","journal-title":"Mol. Biol. Evol."},{"key":"2023013111551721900_B12","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/BF02101694","article-title":"Dating the humanape splitting by a molecular clock of mitochondrial DNA","volume":"22","author":"Hasegawa","year":"1985","journal-title":"J. Mol. Evol."},{"key":"2023013111551721900_B13","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1093\/bioinformatics\/bti100","article-title":"DPRml: distributed phylogeney reconstruction by maximum likelihood","volume":"21","author":"Keane","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013111551721900_B14","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/BF02101990","article-title":"A new method for calculating evolutionary substitution rates","volume":"20","author":"Lanave","year":"1984","journal-title":"J. Mol. Evol."},{"key":"2023013111551721900_B15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2739-5","volume-title":"Mathematical and Statistical Methods for Genetic Analysis.","author":"Lange","year":"1997"},{"key":"2023013111551721900_B16","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/263580.263591","article-title":"Generalized cannon's algorithm for parallel matrix multiplication","volume-title":"ICS '97: Proceedings of the 11th International Conference on Supercomputing.","author":"Lee","year":"1997"},{"key":"2023013111551721900_B17","doi-asserted-by":"crossref","first-page":"S10","DOI":"10.1186\/1471-2105-9-S2-S10","article-title":"CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment","volume":"9","author":"Manavski","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013111551721900_B18","doi-asserted-by":"crossref","first-page":"3794","DOI":"10.1093\/bioinformatics\/bti594","article-title":"pIQPNNI: parallel reconstruction of large maximum likelihood phylogenies","volume":"21","author":"Minh","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013111551721900_B19","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1109\/JPROC.1998.658762","article-title":"Cramming more components onto integrated circuits","volume":"86","author":"Moore","year":"1998","journal-title":"Proc. IEEE"},{"key":"2023013111551721900_B20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1014362705613","article-title":"High-performance algorithm engineering for computational phylogenetics","volume":"22","author":"Moret","year":"2002","journal-title":"J. Supercomput."},{"key":"2023013111551721900_B21","first-page":"715","article-title":"A likelihood approach for comparing synonymous and nonsynonymous nucleotide substitution rates, with applications to the chloroplast genome","volume":"11","author":"Muse","year":"1994","journal-title":"Mol. Biol. Evol."},{"key":"2023013111551721900_B22","volume-title":"NVIDIA CUDA Compute Unified Device Architecture: Programming Guide Version 2.0.","author":"NVIDIA","year":"2008"},{"key":"2023013111551721900_B23","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1080\/10635150500354688","article-title":"An empirical examination of the utility of codon-substitution models in phylogeny reconstruction","volume":"54","author":"Ren","year":"2005","journal-title":"Syst. Biol."},{"key":"2023013111551721900_B24","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1101\/gr.8.3.222","article-title":"Computational advances in maximum likelihood methods for molecular phylogeny","volume":"8","author":"Schadt","year":"1998","journal-title":"Genome Res."},{"key":"2023013111551721900_B25","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1093\/bioinformatics\/18.3.502","article-title":"TREE-PUZZLE: maximum likelihood phylogenetic analysis using quartets and parallel computing","volume":"18","author":"Schmidt","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013111551721900_B26","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1093\/molbev\/msj021","article-title":"Choosing appropriate substitution models for the phylogenetic anaylsis of protein-coding sequences","volume":"23","author":"Shapiro","year":"2006","journal-title":"Mol. Biol. Evol."},{"key":"2023013111551721900_B27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/1375527.1375572","article-title":"Efficient computation of sum-products on GPUs through software-managed cache","volume-title":"Proceedings of the 22nd Annual International Conference on Supercomputing.","author":"Silberstein","year":"2008"},{"key":"2023013111551721900_B28","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/bioinformatics\/bti191","article-title":"RAxML-III: a fast program for maximum likelihood-based inference of large phylogenetic trees","volume":"21","author":"Stamatakis","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013111551721900_B29","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF00178256","article-title":"Estimating the pattern of nucleotide substitution","volume":"39","author":"Yang","year":"1994","journal-title":"J. Mol. Evol."},{"key":"2023013111551721900_B30","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s002390010105","article-title":"Maximum likelihood estimation on large phylogeneis and analysis of adaptive evolution in human influenza virus A","volume":"51","author":"Yang","year":"2000","journal-title":"J. Mol. Evol."},{"key":"2023013111551721900_B31","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":"2023013111551721900_B32","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1016\/j.ympev.2004.08.001","article-title":"Phylogenetic relationships within mammalian order Carnivore indicated by sequences of two nuclear DNA genes","volume":"33","author":"Yu","year":"2004","journal-title":"Mol. Phylogenet. Evol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/11\/1370\/48988217\/bioinformatics_25_11_1370.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/11\/1370\/48988217\/bioinformatics_25_11_1370.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T16:02:03Z","timestamp":1675180923000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/11\/1370\/332982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,15]]},"references-count":32,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2009,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp244","relation":{"has-review":[{"id-type":"doi","id":"10.3410\/f.1804956.1338054","asserted-by":"object"}]},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,6,1]]},"published":{"date-parts":[[2009,4,15]]}}}