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.

See Usage Policy.


Use this Persistent URL to link to this item:


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
Related URLs:
URLURL TypeDescription
Vaidyanathan, P. P.0000-0003-3003-7042
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9709
Deposited On:10 Mar 2008
Last Modified:08 Nov 2021 21:01

Repository Staff Only: item control page