Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 27, 2003 | Published
Journal Article Open

HMM sampling and applications to gene finding and alternative splicing

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.

Additional Information

© 2003 Oxford University Press. Received on March 17, 2003; accepted on June 9, 2003. The authors would like to thank Michael Siani-Rose for useful discussions. This work was partially supported by NIH grant R01-HG02362-01.

Attached Files

Published - btg1057.pdf

Files

btg1057.pdf
Files (89.5 kB)
Name Size Download all
md5:62b59fabf1808fa2abd60167182e99ae
89.5 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023