一种在格点模型上模拟蛋白质折叠结构的优化算法

An Optimization Algorithm for Simulating Protein Folding Structures in Lattice Models

蛋白质折叠问题是生物信息学中一个经典的多项式复杂程度的非确定性(non-deterministic polynomial,NP)难度问题.势能曲面变平法(ELP)是一种启发式的全局优化算法.通过对ELP方法中的直方图函数提出一种新的更新机制,并将基于贪心策略的初始构象的产生,基于牵引移动的邻域搜索策略与ELP方法相结合,为面心立方体(FCC)格点模型的蛋白质折叠问题提出一种改进的势能曲面变平(ELP+)算法.采用文献中9条常用序列作为测试集.对于每条序列,ELP+算法均能找到与文献中的算法所得到的最低能量相等或更低的能量.实验结果表明,ELP+算法是求解FCC格点模型的蛋白质折叠问题的一种有效算法.

Protein folding problem is a classical non-deterministic polynomial （NP） hard problem in bioinformatics. The energy landscape paving （ELP） method is a class of heuristic global optimization algorithm. This paper applies the ELP method to simulate protein folding conformations for the hydrophobic-polar （HP） model on the face-centered-cube （FCC） lattice. By putting forward a new update mechanism of the histogram function in ELP and incorporating the generation of initial conformation based on the greedy strategy and the neighborhood search strategy based on pull-moves into ELP, an improved energy landscape paving （ELP＋） method is put forward for the protein folding problem on the FCC lattice model. We test the method on nine benchmark sequences. The lowest energies by ELP＋ are as good as or better than those of other methods in the literature for all instances. Computational results show that ELP＋ is an effective method for protein folding problem on FCC lattice model.