Bioinformatics Vol. 19 Suppl. 2 2003
pages ii36-ii41
© 2003 Oxford University Press
HMM sampling and applications to gene finding and alternative splicing
1 Affymetrix, 6550 Vallejo St Suite 100,
Emeryville, CA 94608, USA
2 Department of Mathematics, U.C. Berkeley,
CA 94720, USA
Received on March 17, 2003
; accepted on June 9, 2003
The standard method of applying hidden Markov models to biological problems is to find a Viterbi (maximal weight) path through the HMM graph. The Viterbi algorithm reduces the problem of finding the most likely hidden state sequence that explains given observations, to a dynamic programming problem for corresponding directed acyclic graphs. For example, in the gene finding application, the HMM is used to find the most likely underlying gene structure given a DNA sequence. In this note we discuss the applications of sampling methods for HMMs. The standard sampling algorithm for HMMs is a variant of the common forward-backward and backtrack algorithms, and has already been applied in the context of Gibbs sampling methods. Nevetheless, the practice of sampling state paths from HMMs does not seem to have been widely adopted, and important applications have been overlooked. We show how sampling can be used for finding alternative splicings for genes, including alternative splicings that are conserved between genes from related organisms. We also show how sampling from the posterior distribution is a natural way to compute probabilities for predicted exons and gene structures being correct under the assumed model. Finally, we describe a new memory efficient sampling algorithm for certain classes of HMMs which provides a practical sampling alternative to the Hirschberg algorithm for optimal alignment. The ideas presented have applications not only to gene finding and HMMs but more generally to stochastic context free grammars and RNA structure prediction.
Key words: suboptimal parses, sampling, hidden Markov model, conserved alternative splicing
Contact: lpachter{at}math.berkeley.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  W. Boomsma, K. V. Mardia, C. C. Taylor, J. Ferkinghoff-Borg, A. Krogh, and T. Hamelryck A generative, probabilistic model of local protein structure PNAS, July 1, 2008; 105(26): 8932 - 8937. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Stanke, M. Diekhans, R. Baertsch, and D. Haussler Using native and syntenically mapped cDNA alignments to improve de novo gene finding Bioinformatics, March 1, 2008; 24(5): 637 - 644. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Stanke, O. Keller, I. Gunduz, A. Hayes, S. Waack, and B. Morgenstern AUGUSTUS: ab initio prediction of alternative transcripts. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W435 - W439. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Agrawal and G. D. Stormo Using mRNAs lengths to accurately predict the alternatively spliced gene products in Caenorhabditis elegans Bioinformatics, May 15, 2006; 22(10): 1239 - 1244. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Larranaga, B. Calvo, R. Santana, C. Bielza, J. Galdiano, I. Inza, J. A. Lozano, R. Armananzas, G. Santafe, A. Perez, et al. Machine learning in bioinformatics Brief Bioinform, March 1, 2006; 7(1): 86 - 112. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S.-J. Noh, K. Lee, H. Paik, and C.-G. Hur TISA: Tissue-specific Alternative Splicing in Human and Mouse Genes DNA Res, January 1, 2006; 13(5): 229 - 243. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Dewey, J. Q. Wu, S. Cawley, M. Alexandersson, R. Gibbs, and L. Pachter Accurate Identification of Novel Human Genes Through Simultaneous Gene Prediction in Human, Mouse, and Rat Genome Res., April 1, 2004; 14(4): 661 - 664. [Abstract] [Full Text] [PDF]
|
|