CaltechAUTHORS
  A Caltech Library Service

Optimal alignment algorithm for context-sensitive hidden Markov models

Yoon, Byung-Jun and Vaidyanathan, P. P. (2005) Optimal alignment algorithm for context-sensitive hidden Markov models. In: IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005 (ICASSP '05), Philadelphia, PA, 18-23 March 2005. Vol.4. IEEE , Piscataway, NJ, IV-293-IV-296. ISBN 0780388747 http://resolver.caltech.edu/CaltechAUTHORS:YOOicassp05

[img]
Preview
PDF
See Usage Policy.

250Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:YOOicassp05

Abstract

The hidden Markov model is well-known for its efficiency in modeling short-term dependencies between adjacent samples. However, it cannot be used for modeling longer-range interactions between symbols that are distant from each other. In this paper, we introduce the concept of context-sensitive HMM that is capable of modeling strong pairwise correlations between distant symbols. Based on this model, we propose a polynomial-time algorithm that can be used for finding the optimal state sequence of an observed symbol string. The proposed model is especially useful in modeling palindromes, which has an important application in RNA secondary structure analysis.


Item Type:Book Section
Additional Information:© 2005 IEEE. Reprinted with Permission. Publication Date: 18-23 March 2005. Posted online: 2005-05-09. Work supported in part by the ONR grant N00014-99-1-1002 and by the NSF grant CCF-0428326, USA.
Subject Keywords:biology computing; computational complexity; correlation methods; hidden Markov models; macromolecules; optimization; sequences; RNA secondary structure analysis; context-sensitive HMM; context-sensitive models; distant symbols; hidden Markov models; observed symbol string; optimal alignment algorithm; optimal state sequence; palindromes; polynomial-time algorithm; strong pairwise correlations
Record Number:CaltechAUTHORS:YOOicassp05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:YOOicassp05
Alternative URL:http://dx.doi.org/10.1109/ICASSP.2005.1416003
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9709
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:10 Mar 2008
Last Modified:26 Dec 2012 09:51

Repository Staff Only: item control page