Publication details

Brona Brejova, Daniel G. Brown, Tomas Vinar. The most probable labeling problem in HMMs and its application to bioinformatics. In I. Jonassen, J. Kim, ed., Algorithms in Bioinformatics, 4th International Workshop (WABI), 3240 volume of Lecture Notes in Bioinformatics, pp. 426-437, Bergen, Norway, September 2004. Springer.
Preprint, 263Kb | Download from publisher | BibTeX | MathSciNet

Abstract

Hidden Markov models (HMMs) are often used for biological sequence 
annotation. Each sequence element is represented by states with the same 
label. A sequence should be annotated with the labeling of highest 
probability. Computing this most probable labeling was shown
NP-hard by Lyngsoe and Pedersen. We improve this result by proving the 
problem NP-hard for a fixed HMM. High probability labelings are often found 
by heuristics, such as taking the labeling corresponding to the most probable 
state path. We introduce an efficient algorithm that computes the most 
probable labeling for a wide class of HMMs, including models previously used 
for transmembrane protein topology prediction and coding region detection.