求解HP格点模型的最佳优先搜索算法  

Best-First Search Algorithm for Solving HP Lattice Model

作　　者：陈昊[1] 黄文奇[2] 

机构地区：[1]湖北大学数学与计算机科学学院,武汉430062 [2]华中科技大学计算机学院,武汉430074

出　　处：《计算机工程与应用》2006年第36期49-50,72,共3页Computer Engineering and Applications

基　　金：国家973重点基础研究发展规划资助项目(G1998030600)

摘　　要：HP格点模型是目前预测蛋白质折叠结构的一种最简单和最流行的模型,该模型已被证明是NP完全问题。将问题的解空间组织成树型结构,利用启发式规则—k步探测法对结点的可能分支进行评估,采用最佳优先策略搜索解空间树。最后用最佳优先搜索算法(BF)对一组公认的算例进行了实算,计算结果表明,BF计算效率优于传统的遗传算法和Monte Carlo方法。Hydrophobic-hydrophilic lattice model （HP model） is one of the most simplified and popular models of protein folding prediction,the protein folding problem under the HP model has been proved to be NP-complete.As feasible solution sets of this problem can be organized as a tree structure,we use Best-First search strategy（BF） to traverse the tree,for which we propose an effective heuristic rule called k steps exploration.A group of recognized instances has been calculated,computational results demonstrate that BF is superior to conventional genetic algorithms and Monte Carlo methods.

关 键 词：格点模型 NP难度 最佳优先搜索 启发规则 构形 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]