Computational Biology
@ Comenius University in Bratislava

Brona Brejova, Daniel G. Brown, Tomas Vinar. The Most Probable Labeling Problem in HMMs and Its Applications to Bioinformatics. In Inge Jonassen, Junhyong Kim, ed., Algorithms in Bioinformatics (WABI 2004), 3240 volume of Lecture Notes in Bioinformatics, pp. 426-437, Bergen, Norway, 2004. Springer.

Download preprint: 04wabi.pdf, 263Kb

Download from publisher: http://springerlink.metapress.com/link.asp?id=mcp4bj4g5c00n4ya

Related web page: not available

Bibliography entry: BibTeX

See also: early version

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 (2002). 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.