New decoding algorithms for Hidden Markov Models using distance measures on labellings

BMC Bioinformatics

Research

Daniel G Brown¹  Jakub Truszkowski¹ 

[1] David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada;

关键词: Local Search;    Hide Markov Model;    Transmembrane Helix;    Local Search Algorithm;    State Path;   

DOI  :  10.1186/1471-2105-11-S1-S40

来源: Springer

【 摘 要 】

BackgroundExisting hidden Markov model decoding algorithms do not focus on approximately identifying the sequence feature boundaries.ResultsWe give a set of algorithms to compute the conditional probability of all labellings "near" a reference labelling λ 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.ConclusionMore robust HMM decoding may allow for better analysis of sequence features, in reasonable runtimes.

【 授权许可】

CC BY   
© Brown and Truszkowski; licensee BioMed Central Ltd. 2010