Skip Navigation



Bioinformatics Advance Access published online on February 24, 2005
Bioinformatics, doi:10.1093/bioinformatics/bti177
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow Supplementary data
Right arrow All Versions of this Article:
21/10/2294    most recent
bti177v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Holmes, I.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Holmes, I.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2005). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oupjournals.org
Received July 20, 2004
Revised November 19, 2004
Accepted November 22, 2004

Article

Using evolutionary Expectation Maximisation to estimate indel rates

Ian Holmes 1*

1 Department of Statistics, 1 South Parks Road, Oxford OX1 3TG, UK

* To whom correspondence should be addressed.
Ian Holmes, E-mail: ihh{at}berkeley.edu


  Abstract

Motivation: The Expectation Maximisation algorithm, in the form of the Baum-Welch algorithm (for HMMs) or the Inside-Outside algorithm (for SCFGs), is a powerful way to estimate the parameters of stochastic grammars for biological sequence analysis. To use this algorithm for multiplesequence evolutionary modeling, it would be useful to apply the EM algorithm to estimate not just 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 Expectation Maximisation, under the single-residue indel model due 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). Due 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.

Availability: Software implementing the algorithm and the benchmark is available under GPL from http://www.biowiki.org/.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 BioinformaticsHome page
R. Satija, L. Pachter, and J. Hein
Combining statistical alignment and phylogenetic footprinting to detect regulatory elements
Bioinformatics, May 15, 2008; 24(10): 1236 - 1242.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
R. K. Bradley and I. Holmes
Transducers: an emerging probabilistic framework for modeling indels on trees
Bioinformatics, December 1, 2007; 23(23): 3258 - 3262.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
I. Holmes
Phylocomposer and phylodirector: analysis and visualization of transducer indel models
Bioinformatics, December 1, 2007; 23(23): 3263 - 3264.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
L. Carmel, Y. I. Wolf, I. B. Rogozin, and E. V. Koonin
Three distinct modes of intron dynamics in the evolution of eukaryotes
Genome Res., July 1, 2007; 17(7): 1034 - 1044.
[Abstract] [Full Text] [PDF]

Home page
 GeneticsHome page
M. Brandstrom and H. Ellegren
The Genomic Landscape of Short Insertion and Deletion Polymorphisms in the Chicken (Gallus gallus) Genome: A High Frequency of Deletions in Tandem Duplicates
Genetics, July 1, 2007; 176(3): 1691 - 1701.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.