title: Using evolutionary Expectation Maximization to estimate indel rates.
abstract: BACKGROUND
  The Expectation Maximization (EM) algorithm, in the form of the Baum-Welch 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.
  
  
  RESULTS
  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 'TKF91' 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-Welch algorithm for training hidden Markov models, it can be used in an 'unsupervised' fashion to estimate rates for unaligned sequences, or estimate several sets of rates for sequences with heterogenous rates.
  
  
  BACKGROUND
  Software implementing the algorithm and the benchmark is available under GPL from http://www.biowiki.org/
authors.affiliation: Department of Statistics, 1 South Parks Road, Oxford OX1 3TG, UK. ihh@berkeley.edu
authors.forename: Ian
authors.initials: I
authors.lastname: Holmes
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D003198:Computer Simulation; D004252:DNA Mutational Analysis / Q000379:methods*; D004251:DNA Transposable Elements / Q000235:genetics; D019143:Evolution, Molecular; D016013:Likelihood Functions; D008390:Markov Chains; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D017384:Sequence Deletion / Q000235:genetics
chemical_list: D004251:DNA Transposable Elements
references.citation: Mol Biol Evol. 2004 Mar;21(3):529-40
references.pmid: 14694074
references.citation: J Mol Evol. 2001 Dec;53(6):660-9
references.pmid: 11677626
references.citation: Bioinformatics. 2001 Sep;17(9):803-20
references.pmid: 11590097
references.citation: Mol Biol Evol. 2004 Mar;21(3):468-88
references.pmid: 14660683
references.citation: Mol Biol Evol. 2000 Jan;17(1):189-97
references.pmid: 10666718
references.citation: J Mol Biol. 2002 Apr 12;317(5):753-64
references.pmid: 11955022
references.citation: Bioinformatics. 2004 Aug 4;20 Suppl 1:i216-23
references.pmid: 15262802
references.citation: Pac Symp Biocomput. 2001;:179-90
references.pmid: 11262938
references.citation: J Mol Biol. 2003 Oct 17;333(2):453-60
references.pmid: 14529629
references.citation: Nucleic Acids Res. 1999 Jan 1;27(1):260-2
references.pmid: 9847196
references.citation: Science. 2003 May 30;300(5624):1399-404
references.pmid: 12730501
references.citation: BMC Bioinformatics. 2004 Oct 26;5:166
references.pmid: 15507142
references.citation: Mol Biol Evol. 1996 May;13(5):666-73
references.pmid: 8676741
references.citation: J Mol Evol. 1991 Aug;33(2):114-24
references.pmid: 1920447
references.citation: Nature. 2003 May 15;423(6937):241-54
references.pmid: 12748633
references.citation: J Mol Evol. 1992 Jan;34(1):3-16
references.pmid: 1556741
references.citation: J Mol Biol. 2000 Sep 8;302(1):265-79
references.pmid: 10964574