The k-best paths in Hidden Markov Models. Algorithms and Applications to TransmembraneProtein Topology Recognition.

HMM;k-best paths;transmembrane topology;Computer Science

Golod, Daniil

University of Waterloo

关键词: HMM;    k-best paths;    transmembrane topology;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4603/1/thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Traditional algorithms for hidden Markov model decoding seek to maximizeeither the probability of a state path or the number of positions of a sequenceassigned to the correct state. These algorithms provide only a single answer andin practice do not produce good results. The most mathematically sound of thesealgorithms is the Viterbi algorithm, which returns the state path that has thehighest probability of generating a given sequence. Here, we explore an extension tothis algorithm that allows us to find the k paths of highest probabilities. The naiveimplementation of k best Viterbi paths is highly space-inefficient, so we adapt recentwork on the Viterbi algorithm for a single path to this domain. Out algorithm usesmuch less memory than the naive approach. We then investigate the usefulnessof the k best Viterbi paths on the example of transmembrane protein topologyprediction. For membrane proteins, even simple path combination algorithms givegood explanations, and if we look at the paths we are combining, we can give asense of confidence in the explanation as well. For proteins with two topologies,the k best paths can give insight into both correct explanations of a sequence, afeature lacking from traditional algorithms in this domain.