求解HP模型蛋白质折叠问题的启发式算法

Heuristic Algorithm for Protein Folding Problem of HP Model

构造了一个新的数学模型,把三维HP模型的蛋白质折叠问题由一个有约束的优化问题转化为无约束的优化问题,通过建立相对坐标和邻域结构,提出了一个局部搜索算法,并对文献中的链长不同的7个算例进行了测试。结果表明,该算法能在较短时间内找到其中5个算例的最优能量构形,对另外2个难例,则可以找到能量仅比最优构形高一个单位的次优构形。

A heuristic algorithm is proposed in this paper for the HP model protein folding problem. By constructing a new mathematical model, the three dimensional protein folding problem of HP model is converted from a nonlinear constraint-satisfied problem to an unconstrained optimization problem, which can be solved by the local search strategy based on the relative coordinate system and a novel neighbor structure. The computational results on seven benchmark sequences have shown that our algorithm is quite efficient, which can find optimal conformation for five sequences and near-optimal conformation for the other two harder sequences in very short time.