title: New decoding algorithms for Hidden Markov Models using distance measures on labellings.
abstract: 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.
authors.affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada. browndg@uwaterloo.ca
authors.forename: Daniel G
authors.initials: DG
authors.lastname: Brown
authors.forename: Jakub
authors.initials: J
authors.lastname: Truszkowski
mesh_terms: D000465:Algorithms; D030562:Databases, Protein; D008390:Markov Chains; D008565:Membrane Proteins / Q000737:chemistry*
chemical_list: D008565:Membrane Proteins