HMM sampling and applications to gene finding and alternative splicing
Authors:
Open Access
- 27 September 2003
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 19 (suppl_2) , ii36-ii41
Abstract
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@math.berkeley.eduKeywords
This publication has 20 references indexed in Scilit:
- A genomic view of alternative splicingNature Genetics, 2002
- On Near-Optimal Alignments of Biological SequencesJournal of Computational Biology, 1994
- A simple method to generate non-trivial alternate alignments of protein sequencesJournal of Molecular Biology, 1991
- A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisonsJournal of Molecular Biology, 1987
- Implementation of algorithms forK shortest loopless pathsNetworks, 1986
- A dynamic programming algorithm to find all solutions in a neighborhood of the optimumMathematical Biosciences, 1985
- Sequence alignments in the neighborhood of the optimum with general application to dynamic programmingProceedings of the National Academy of Sciences, 1983
- On algorithms for finding the k shortest paths in a networkNetworks, 1979
- CalculatingKth Shortest PathsINFOR: Information Systems and Operational Research, 1973
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970