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
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.