{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T17:10:20Z","timestamp":1760980220312,"version":"3.32.0"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T00:00:00Z","timestamp":1109203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>The Expectation Maximization (EM) algorithm, in the form of the Baum\u2013Welch algorithm (for hidden Markov models) or the Inside-Outside algorithm (for stochastic context-free grammars), is a powerful way to estimate the parameters of stochastic grammars for biological sequence analysis. To use this algorithm for multiple-sequence evolutionary modelling, it would be useful to apply the EM algorithm to estimate not only the probability parameters of the stochastic grammar, but also the instantaneous mutation rates of the underlying evolutionary model (to facilitate the development of stochastic grammars based on phylogenetic trees, also known as Statistical Alignment). Recently, we showed how to do this for the point substitution component of the evolutionary process; here, we extend these results to the indel process.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We present an algorithm for maximum-likelihood estimation of insertion and deletion rates from multiple sequence alignments, using EM, under the single-residue indel model owing to Thorne, Kishino and Felsenstein (the \u2018TKF91\u2019 model). The algorithm converges extremely rapidly, gives accurate results on simulated data that are an improvement over parsimonious estimates (which are shown to underestimate the true indel rate), and gives plausible results on experimental data (coronavirus envelope domains). Owing to the algorithm's close similarity to the Baum\u2013Welch algorithm for training hidden Markov models, it can be used in an \u2018unsupervised\u2019 fashion to estimate rates for unaligned sequences, or estimate several sets of rates for sequences with heterogenous rates.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability<\/jats:title><jats:p>Software implementing the algorithm and the benchmark is available under GPL from http:\/\/www.biowiki.org\/<\/jats:p><\/jats:sec><jats:sec><jats:title>Contact<\/jats:title><jats:p>ihh@berkeley.edu<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/bti177","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T01:31:03Z","timestamp":1109295063000},"page":"2294-2300","source":"Crossref","is-referenced-by-count":23,"title":["Using evolutionary Expectation Maximization to estimate indel rates"],"prefix":"10.1093","volume":"21","author":[{"given":"Ian","family":"Holmes","sequence":"first","affiliation":[{"name":"Department of Statistics 1 South Parks Road , Oxford OX1 3TG, UK"}]}],"member":"286","published-online":{"date-parts":[[2005,2,24]]},"reference":[{"key":"2023013107562879700_B1","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1093\/nar\/27.1.260","volume":"27","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023013107562879700_B2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1093\/oxfordjournals.molbev.a026231","volume":"17","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023013107562879700_B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","year":"1977","journal-title":"J. R. Stat. Soc. B"},{"volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","year":"1998","key":"2023013107562879700_B4"},{"volume-title":"Inferring Phylogenies","year":"2003","key":"2023013107562879700_B5"},{"year":"2001","key":"2023013107562879700_B6"},{"first-page":"179","volume-title":"Pacific Symposium on Biocomputing","year":"2001","key":"2023013107562879700_B7"},{"key":"2023013107562879700_B8","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/jmbi.2000.4061","volume":"302","year":"2000","journal-title":"J. Mol. Biol."},{"year":"2003","key":"2023013107562879700_B9","first-page":"147"},{"volume":"5","journal-title":"BMC Bioinformatics","year":"2004","key":"2023013107562879700_B10"},{"key":"2023013107562879700_B11","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1093\/bioinformatics\/17.9.803","volume":"17","year":"2001","journal-title":"Bioinformatics"},{"key":"2023013107562879700_B12","first-page":"757","volume":"317","year":"2002","journal-title":"J. Mol. Biol."},{"volume-title":"A First Course in Stochastic Processes","year":"1975","key":"2023013107562879700_B13"},{"key":"2023013107562879700_B14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1038\/nature01644","volume":"423","year":"2003","journal-title":"Nature"},{"key":"2023013107562879700_B15","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1016\/j.jmb.2003.08.015","volume":"333","year":"2003","journal-title":"J. Mol. Biol."},{"key":"2023013107562879700_B16","doi-asserted-by":"crossref","first-page":"I216","DOI":"10.1093\/bioinformatics\/bth901","volume":"20","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013107562879700_B17","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1126\/science.1085953","volume":"300","year":"2003","journal-title":"Science"},{"key":"2023013107562879700_B18","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1007\/s002390010253","volume":"53","year":"2001","journal-title":"J. Mol. Evol."},{"key":"2023013107562879700_B19","first-page":"529","volume":"21","year":"2004","journal-title":"Mol. Biol. Evol."},{"key":"2023013107562879700_B20","first-page":"1139","volume":"41","year":"1995","journal-title":"J. Mol. Evol."},{"volume-title":"Numerical Recipes in C","year":"1992","key":"2023013107562879700_B21"},{"key":"2023013107562879700_B22","first-page":"468","volume":"21","year":"2004","journal-title":"Mol. Biol. Evol."},{"key":"2023013107562879700_B23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/BF02193625","volume":"33","year":"1991","journal-title":"J. Mol. Evol."},{"key":"2023013107562879700_B24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF00163848","volume":"34","year":"1992","journal-title":"J. Mol. Evol."},{"key":"2023013107562879700_B25","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1093\/oxfordjournals.molbev.a025627","volume":"13","year":"1996","journal-title":"Mol. Biol. Evol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/10\/2294\/48971777\/bioinformatics_21_10_2294.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/10\/2294\/48971777\/bioinformatics_21_10_2294.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T21:05:32Z","timestamp":1734987932000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/10\/2294\/205605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2,24]]},"references-count":25,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2005,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti177","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2005,5]]},"published":{"date-parts":[[2005,2,24]]}}}