A new decoding algorithm for hidden Markov models improves the prediction of the topology of all-beta membrane proteins.
A new decoding algorithm for hidden Markov models improves the prediction of the topology of all-beta membrane proteins.
复制标题
DOI：
10.1186/1471-2105-6-s4-s12
复制
发表时间：
2005-12-01
影响因子：
3
通讯作者：
Casadio R
中科院分区：
文献类型：
--
作者：
Fariselli P;Martelli PL;Casadio R
膜蛋白的结构预测仍然是一个具有挑战性的计算问题。隐马尔可夫模型（HMM）已成功地应用于预测膜蛋白拓扑结构的问题。在预测任务中，HMM被赋予解码算法，以便将最可能的状态路径以及标签分配给未知序列。Viterbi和后验译码算法是最常见的。前者是非常有效的，当一个路径占主导地位，而后者，即使不保证保持HMM语法，是更有效的，当几个并发路径具有相似的概率。第三个好的替代方案是1-best，它的性能等于或优于Viterbi。本文介绍了后验维特比译码（PV），它是后验译码和维特比译码相结合的一种新的译码算法。PV是一个两步过程：首先计算每个状态的后验概率，然后通过Viterbi算法评估通过模型的最佳后验允许路径。我们表明，PV解码比其他算法进行测试时，预测的β-桶膜蛋白的拓扑结构的问题。
Structure prediction of membrane proteins is still a challenging computational problem. Hidden Markov models (HMM) have been successfully applied to the problem of predicting membrane protein topology. In a predictive task, the HMM is endowed with a decoding algorithm in order to assign the most probable state path, and in turn the labels, to an unknown sequence. The Viterbi and the posterior decoding algorithms are the most common. The former is very efficient when one path dominates, while the latter, even though does not guarantee to preserve the HMM grammar, is more effective when several concurring paths have similar probabilities. A third good alternative is 1-best, which was shown to perform equal or better than Viterbi. In this paper we introduce the posterior-Viterbi (PV) a new decoding which combines the posterior and Viterbi algorithms. PV is a two step process: first the posterior probability of each state is computed and then the best posterior allowed path through the model is evaluated by a Viterbi algorithm. We show that PV decoding performs better than other algorithms when tested on the problem of the prediction of the topology of beta-barrel membrane proteins.