求解HP模型蛋白质折叠问题的改进PERM算法

PERM是一种用来求解基于HP模型的蛋白质折叠问题的高效算法.在介绍PERM算法核心思想的基础上,对影响算法效率的因素做了改进:重新定义了权重和权重预测公式,并对选择动作时不同情况下的权重计算公式进行了统一,得到了改进的PERM算法.对当前文献中的多个典型算例进行了测试,并与Monte Carlo算法和PERM进行了比较.结果表明, 改进后的PERM算法在计算速度上比PERM有明显提高,在速度和优度上远高于Monte Carlo算法.特别是对链长为46的算例,找到了比文献中报道的结果能量更低的构形.

An Improved PERM Method for Protein Folding Problem of HP Model

Predicting the structure of a protein from its amino acid sequence is one of the central problems in computational biology.PERM(pruned-enrichment Rosenbluth method)is an efficient algorithm for the protein folding problem based on HP lattice model.However,the PERM algorithm is not succinct and is not easily understood.Based on introducing the algorithm idea of PERM and the key factors affecting the efficiency of PERM,a new version of PERM with two improvements is proposed:one is that it redefines the weight and the predicted value in PERM,and the other is that it unifies the calculation of weight when choosing possible branches.The proposed formulae are more succinct and uniform and the algorithm idea is much clearer in the improved PERM.The computational result shows that the improved PERM can find the known lowest energy states for all the test instances.The improved PERM is generally several to hundreds times faster than PERM,and it is far more efficient than Monte Carlo.It is noteworthy that with the improved PERM,lower energy(-35)can be found than the previously best result(-34)in literature for one test instance with length equal to 46.