Title :
Optimal alignment algorithm for context-sensitive hidden Markov models
Author :
Yoon, Byung-Jun ; Vaidyanathan, P.P.
Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
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.
Keywords :
biology computing; computational complexity; correlation methods; hidden Markov models; macromolecules; optimisation; 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; Biological system modeling; Context modeling; Electronic mail; Hidden Markov models; Pairwise error probability; Polynomials; Production; RNA; Sequences; Speech recognition;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on
Print_ISBN :
0-7803-8874-7
DOI :
10.1109/ICASSP.2005.1416003
