Liu Jingfa, Song Beibei, Liu Zhaoxia, Huang Weibo, Sun Yuanyuan, Liu Wenjie
Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science and Technology, Nanjing 210044, China and Network Information Center, Nanjing University of Information Science and Technology, Nanjing 210044, China.
Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science and Technology, Nanjing 210044, China and School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Nov;88(5):052704. doi: 10.1103/PhysRevE.88.052704. Epub 2013 Nov 6.
Protein structure prediction (PSP) is a classical NP-hard problem in computational biology. The energy-landscape paving (ELP) method is a class of heuristic global optimization algorithm, and has been successfully applied to solving many optimization problems with complex energy landscapes in the continuous space. 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. Twelve general benchmark instances are first tested on both two-dimensional and three-dimensional (3D) face-centered-cubic (fcc) hydrophobic-hydrophilic (HP) lattice models. The lowest energies by ELP+ are as good as or better than those of other methods in the literature for all instances. Then, five sets of larger-scale instances, denoted by S, R, F90, F180, and CASP target instances on the 3D FCC HP lattice model are tested. The proposed algorithm finds lower energies than those by the five other methods in literature. Not unexpectedly, this is particularly pronounced for the longer sequences considered. Computational results show that ELP+ is an effective method for PSP on the fcc HP lattice model.
蛋白质结构预测（PSP）是计算生物学中的一个经典NP难问题。能量景观平铺（ELP）方法是一类启发式全局优化算法，已成功应用于解决连续空间中许多具有复杂能量景观的优化问题。通过提出一种新的ELP直方图函数更新机制，并将基于贪婪策略的初始构象生成和基于拉移的邻域搜索策略纳入ELP，提出了一种改进的能量景观平铺（ELP+）方法。首先在二维和三维（3D）面心立方（fcc）疏水-亲水（HP）晶格模型上测试了12个通用基准实例。对于所有实例，ELP+得到的最低能量与文献中其他方法的结果一样好或更好。然后，在3D FCC HP晶格模型上测试了五组更大规模的实例，分别表示为S、R、F90、F180和CASP目标实例。所提出的算法得到的能量比文献中其他五种方法的更低。不出所料，对于所考虑的较长序列，这种情况尤为明显。计算结果表明，ELP+是fcc HP晶格模型上PSP的一种有效方法。
