{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T01:23:58Z","timestamp":1777339438469,"version":"3.51.4"},"reference-count":49,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2016,11,26]],"date-time":"2016-11-26T00:00:00Z","timestamp":1480118400000},"content-version":"vor","delay-in-days":55,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["CR32I3_143768"],"award-info":[{"award-number":["CR32I3_143768"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["IZLRZ3_163872"],"award-info":[{"award-number":["IZLRZ3_163872"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Codon models are widely used to identify the signature of selection at the molecular level and to test for changes in selective pressure during the evolution of genes encoding proteins. The large size of the state space of the Markov processes used to model codon evolution makes it difficult to use these models with large biological datasets. We propose here to use state aggregation to reduce the state space of codon models and, thus, improve the computational performance of likelihood estimation on these models.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We show that this heuristic speeds up the computations of the M0 and branch-site models up to 6.8 times. We also show through simulations that state aggregation does not introduce a detectable bias. We analyzed a real dataset and show that aggregation provides highly correlated predictions compared to the full likelihood computations. Finally, state aggregation is a very general approach and can be applied to any continuous-time Markov process-based model with large state space, such as amino acid and coevolution models. We therefore discuss different ways to apply state aggregation to Markov models used in phylogenetics.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and Implementation<\/jats:title>\n                    <jats:p>The heuristic is implemented in the godon package (https:\/\/bitbucket.org\/Davydov\/godon) and in a version of FastCodeML (https:\/\/gitlab.isb-sib.ch\/phylo\/fastcodeml).<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw632","type":"journal-article","created":{"date-parts":[[2016,9,29]],"date-time":"2016-09-29T15:06:19Z","timestamp":1475161579000},"page":"354-362","source":"Crossref","is-referenced-by-count":8,"title":["State aggregation for fast likelihood computations in molecular evolution"],"prefix":"10.1093","volume":"33","author":[{"given":"Iakov I","family":"Davydov","sequence":"first","affiliation":[{"name":"Department of Ecology and Evolution, Biophore, University of Lausanne, Lausanne, Switzerland"},{"name":"Swiss Institute of Bioinformatics, Genopode, Quartier Sorge, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Robinson-Rechavi","sequence":"additional","affiliation":[{"name":"Department of Ecology and Evolution, Biophore, University of Lausanne, Lausanne, Switzerland"},{"name":"Swiss Institute of Bioinformatics, Genopode, Quartier Sorge, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Salamin","sequence":"additional","affiliation":[{"name":"Department of Ecology and Evolution, Biophore, University of Lausanne, Lausanne, Switzerland"},{"name":"Swiss Institute of Bioinformatics, Genopode, Quartier Sorge, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,10,2]]},"reference":[{"key":"2023020204410022800_btw632-B1","author":"Aldous","year":"2002"},{"key":"2023020204410022800_btw632-B2","doi-asserted-by":"crossref","first-page":"D662","DOI":"10.1093\/nar\/gku1010","article-title":"Ensembl 2015","volume":"43","author":"Cunningham","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023020204410022800_btw632-B3","doi-asserted-by":"crossref","first-page":"2989","DOI":"10.1093\/bioinformatics\/bts555","article-title":"Phylogenetics, likelihood, evolution and complexity","volume":"28","author":"de Koning","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B4","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1093\/bioinformatics\/btu012","article-title":"Evolutionary footprint of coevolving positions in genes","volume":"30","author":"Dib","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B5","doi-asserted-by":"crossref","first-page":"240","DOI":"10.2307\/2412304","article-title":"Maximum likelihood and minimum-steps methods for estimating evolutionary trees from data on discrete characters","volume":"22","author":"Felsenstein","year":"1973","journal-title":"Syst. Zool"},{"key":"2023020204410022800_btw632-B6","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":"2023020204410022800_btw632-B7","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1111\/j.1096-0031.1997.tb00239.x","article-title":"Efficient incremental character optimization","volume":"13","author":"Gladstein","year":"1997","journal-title":"Cladistics"},{"key":"2023020204410022800_btw632-B8","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":"2023020204410022800_btw632-B9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1111\/j.1096-0031.1993.tb00236.x","article-title":"Character optimization and calculation of tree lengths","volume":"9","author":"Goloboff","year":"1993","journal-title":"Cladistics"},{"key":"2023020204410022800_btw632-B10","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1080\/10635150390235520","article-title":"A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood","volume":"52","author":"Guindon","year":"2003","journal-title":"Syst. Biol"},{"key":"2023020204410022800_btw632-B11","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/sysbio\/syq010","article-title":"New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0","volume":"59","author":"Guindon","year":"2010","journal-title":"Syst. Biol"},{"key":"2023020204410022800_btw632-B12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/978-1-4615-2241-6_12","volume-title":"Computations with Markov Chains","author":"Hillston","year":"1995"},{"key":"2023020204410022800_btw632-B13","doi-asserted-by":"crossref","first-page":"4338","DOI":"10.1093\/bioinformatics\/bti713","article-title":"Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood","volume":"21","author":"Hordijk","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B14","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1093\/bioinformatics\/17.8.754","article-title":"MRBAYES: Bayesian inference of phylogenetic trees","volume":"17","author":"Huelsenbeck","year":"2001","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B15","volume-title":"Finite Markov Chains: With a New Appendix \u201cGeneralization of a Fundamental Matrix\u201d","author":"Kemeny","year":"1983"},{"key":"2023020204410022800_btw632-B16","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1016\/j.jmb.2011.06.005","article-title":"Markovian and non-markovian protein sequence evolution: aggregated markov process models","volume":"411","author":"Kosiol","year":"2011","journal-title":"J. Mol. Biol"},{"key":"2023020204410022800_btw632-B17","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.1089\/cmb.2006.13.1701","article-title":"Conjugate Gibbs sampling for Bayesian phylogenetic models","volume":"13","author":"Lartillot","year":"2006","journal-title":"J. Comput. Biol"},{"key":"2023020204410022800_btw632-B18","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1093\/molbev\/msh112","article-title":"A Bayesian mixture model for across-site heterogeneities in the amino-acid replacement process","volume":"21","author":"Lartillot","year":"2004","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B19","doi-asserted-by":"crossref","first-page":"16366","DOI":"10.1021\/jp063367k","article-title":"Hidden Markov model analysis of multichromophore photobleaching","volume":"110","author":"Messina","year":"2006","journal-title":"J. Phys. Chem. B"},{"key":"2023020204410022800_btw632-B20","doi-asserted-by":"crossref","first-page":"D917","DOI":"10.1093\/nar\/gkt1065","article-title":"Selectome update: quality control and computational improvements to a database of positive selection","volume":"42","author":"Moretti","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023020204410022800_btw632-B21","doi-asserted-by":"crossref","first-page":"e1002764","DOI":"10.1371\/journal.pgen.1002764","article-title":"Detecting individual sites subject to episodic diversifying selection","volume":"8","author":"Murrell","year":"2012","journal-title":"PLoS Genet"},{"key":"2023020204410022800_btw632-B22","first-page":"715","article-title":"A likelihood approach for comparing synonymous and nonsynonymous nucleotide substitution rates, with application to the chloroplast genome","volume":"11","author":"Muse","year":"1994","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B23","first-page":"msu300","article-title":"IQ-TREE: a fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies","author":"Nguyen","year":"2014","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.entcs.2012.05.018","article-title":"Model decomposition and stochastic fragments","volume":"284","author":"Petrov","year":"2012","journal-title":"Electr. Notes Theor. Comput. Sci"},{"key":"2023020204410022800_btw632-B25","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1093\/molbev\/msh137","article-title":"Genome-scale phylogeny and the detection of systematic biases","volume":"21","author":"Phillips","year":"2004","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B26","doi-asserted-by":"crossref","first-page":"D404","DOI":"10.1093\/nar\/gkn768","article-title":"Selectome: a database of positive selection","volume":"37","author":"Proux","year":"2009","journal-title":"Nucleic Acids Res"},{"key":"2023020204410022800_btw632-B27","doi-asserted-by":"crossref","first-page":"3862","DOI":"10.1002\/sim.5808","article-title":"State-space size considerations for disease-progression models","volume":"32","author":"Regnier","year":"2013","journal-title":"Stat. Med"},{"key":"2023020204410022800_btw632-B28","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":"2023020204410022800_btw632-B29","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1093\/bioinformatics\/btm532","article-title":"Uniformization for sampling realizations of Markov processes: applications to Bayesian implementations of codon substitution models","volume":"24","author":"Rodrigue","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B30","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1111\/j.1096-0031.1998.tb00346.x","article-title":"Fast Fitch-parsimony algorithms for large data sets","volume":"14","author":"Ronquist","year":"1998","journal-title":"Cladistics"},{"key":"2023020204410022800_btw632-B31","doi-asserted-by":"crossref","first-page":"3297","DOI":"10.1093\/molbev\/msr162","article-title":"Evolutionary models accounting for layers of selection in protein-coding genes and their impact on the inference of positive selection","volume":"28","author":"Rubinstein","year":"2011","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B32","first-page":"706","author":"Schabauer","year":"2012"},{"key":"2023020204410022800_btw632-B33","doi-asserted-by":"crossref","first-page":"1342","DOI":"10.1093\/molbev\/msv022","article-title":"Less is more: an adaptive branch-site random effects model for efficient detection of episodic diversifying selection","volume":"32","author":"Smith","year":"2015","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B34","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":"2023020204410022800_btw632-B35","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":"2023020204410022800_btw632-B36","first-page":"193","author":"Stamatakis","year":"2004"},{"key":"2023020204410022800_btw632-B37","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1111\/j.1467-9868.2004.00439.x","article-title":"Strong control, conservative point estimation and simultaneous conservative consistency of false discovery rates: a unified approach","volume":"66","author":"Storey","year":"2004","journal-title":"J. R. Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"2023020204410022800_btw632-B38","doi-asserted-by":"crossref","first-page":"2139","DOI":"10.1093\/molbev\/msm144","article-title":"On reduced amino acid alphabets for phylogenetic inference","volume":"24","author":"Susko","year":"2007","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B39","first-page":"411","volume-title":"Molecular Systematics","author":"Swofford","year":"1990"},{"key":"2023020204410022800_btw632-B40","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.jtbi.2012.07.007","article-title":"Simplification of reversible Markov chains by removal of states with low equilibrium occupancy","volume":"311","author":"Ullah","year":"2012","journal-title":"J. Theor. Biol"},{"key":"2023020204410022800_btw632-B41","first-page":"btt760.","article-title":"Optimization strategies for fast detection of positive selection on phylogenetic trees","author":"Valle","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020204410022800_btw632-B42","doi-asserted-by":"crossref","first-page":"S8,","DOI":"10.1186\/1471-2105-15-S2-S8","article-title":"Statistical tests to identify appropriate types of nucleotide sequence recoding in molecular phylogenetics","volume":"15","author":"Vera-Ruiz","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020204410022800_btw632-B43","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1101\/gr.073585.107","article-title":"EnsemblCompara GeneTrees: complete, duplication-aware phylogenetic trees in vertebrates","volume":"19","author":"Vilella","year":"2009","journal-title":"Genome Res"},{"key":"2023020204410022800_btw632-B44","first-page":"msu400","article-title":"Relax: detecting relaxed selection in a phylogenetic framework","author":"Wertheim","year":"2014","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B45","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1534\/genetics.104.031153","article-title":"Accuracy and power of statistical methods for detecting adaptive evolution in protein coding sequences and for identifying positively selected sites","volume":"168","author":"Wong","year":"2004","journal-title":"Genetics"},{"key":"2023020204410022800_btw632-B46","doi-asserted-by":"crossref","first-page":"1586","DOI":"10.1093\/molbev\/msm088","article-title":"PAML 4: phylogenetic analysis by maximum likelihood","volume":"24","author":"Yang","year":"2007","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B47","doi-asserted-by":"crossref","first-page":"1600","DOI":"10.1093\/oxfordjournals.molbev.a025888","article-title":"Models of amino acid substitution and applications to mitochondrial protein evolution","volume":"15","author":"Yang","year":"1998","journal-title":"Mol. Biol. Evol"},{"key":"2023020204410022800_btw632-B48","doi-asserted-by":"crossref","first-page":"e211.","DOI":"10.1371\/journal.pcbi.0030211","article-title":"Detecting coevolution in and among protein domains","volume":"3","author":"Yeang","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023020204410022800_btw632-B49","doi-asserted-by":"crossref","first-page":"2472","DOI":"10.1093\/molbev\/msi237","article-title":"Evaluation of an improved branch-site likelihood method for detecting positive selection at the molecular level","volume":"22","author":"Zhang","year":"2005","journal-title":"Mol. Biol. Evol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/3\/354\/49037551\/bioinformatics_33_3_354.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/3\/354\/49037551\/bioinformatics_33_3_354.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T23:45:02Z","timestamp":1675295102000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/3\/354\/2584480"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2016,10,2]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw632","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/035063","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,2,1]]},"published":{"date-parts":[[2016,10,2]]}}}