Optimal Alignment Algorithm for Context-Sensitive Hidden Markov Models Conference Paper uri icon


  • 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. © 2005 IEEE.

author list (cited authors)

  • Yoon, B., & Vaidyanathan, P. P.

citation count

  • 5

publication date

  • January 2005