New decoding algorithms for Hidden Markov Models using distance measures on labellings.
BACKGROUND
Existing hidden Markov model decoding algorithms do not focus on approximately identifying the sequence feature boundaries.


RESULTS
We give a set of algorithms to compute the conditional probability of all labellings "near" a reference labelling lambda for a sequence y for a variety of definitions of "near". In addition, we give optimization algorithms to find the best labelling for a sequence in the robust sense of having all of its feature boundaries nearly correct. Natural problems in this domain are NP-hard to optimize. For membrane proteins, our algorithms find the approximate topology of such proteins with comparable success to existing programs, while being substantially more accurate in estimating the positions of transmembrane helix boundaries.


CONCLUSIONS
More robust HMM decoding may allow for better analysis of sequence features, in reasonable runtimes.
Brown
Daniel G
DG
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada. browndg@uwaterloo.ca
Truszkowski
Jakub
J
D000465:Algorithms; D030562:Databases, Protein; D008390:Markov Chains; D008565:Membrane Proteins / Q000737:chemistry*
D008565:Membrane Proteins