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

An Improved PERM Method for Protein Folding Problem of HP Model

作　　者：陈矛[1,2] 黄文奇[2] 吕志鹏[2] 

机构地区：[1]华中师范大学教育信息技术工程研究中心,武汉430079 [2]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机研究与发展》2007年第9期1456-1461,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(10471051);国家"九七三"重点基础研究发展规划基金项目(2004CB318000)

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

关 键 词：NP难 蛋白质折叠 HP模型 增长型算法 PERM算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]