Decoding HMMs using the k best paths: algorithms and applications.

ABSTRACT:

Background

Traditional algorithms for hidden Markov model decoding seek to maximize either the probability of a state path or the number of positions of a sequence assigned to the correct state. These algorithms provide only a single answer and in practice do not produce good results.

Results

We explore an alternative approach, where we efficiently compute the k paths of highest probability to explain a sequence and then either use those paths to explore alternative explanations for a sequence or to combine them into a single explanation. Our procedure uses an online pruning technique to reduce usage of primary memory.

Conclusion

Out algorithm uses much less memory than naive approach. For membrane proteins, even simple path combination algorithms give good explanatio

SUBMITTER: Brown DG 

PROVIDER: S-EPMC3009499 | biostudies-literature | 2010 Jan

REPOSITORIES: biostudies-literature