Zhang Xiaolong, Wang Ting, Luo Huiping, Yang Jack Y, Deng Youping, Tang Jinshan, Yang Mary Qu
School of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan, Hubei, PR China.
BMC Syst Biol. 2010 May 28;4 Suppl 1(Suppl 1):S6. doi: 10.1186/1752-0509-4-S1-S6.
Protein structure prediction (PSP) has important applications in different fields, such as drug design, disease prediction, and so on. In protein structure prediction, there are two important issues. The first one is the design of the structure model and the second one is the design of the optimization technology. Because of the complexity of the realistic protein structure, the structure model adopted in this paper is a simplified model, which is called off-lattice AB model. After the structure model is assumed, optimization technology is needed for searching the best conformation of a protein sequence based on the assumed structure model. However, PSP is an NP-hard problem even if the simplest model is assumed. Thus, many algorithms have been developed to solve the global optimization problem. In this paper, a hybrid algorithm, which combines genetic algorithm (GA) and tabu search (TS) algorithm, is developed to complete this task.
In order to develop an efficient optimization algorithm, several improved strategies are developed for the proposed genetic tabu search algorithm. The combined use of these strategies can improve the efficiency of the algorithm. In these strategies, tabu search introduced into the crossover and mutation operators can improve the local search capability, the adoption of variable population size strategy can maintain the diversity of the population, and the ranking selection strategy can improve the possibility of an individual with low energy value entering into next generation. Experiments are performed with Fibonacci sequences and real protein sequences. Experimental results show that the lowest energy obtained by the proposed GATS algorithm is lower than that obtained by previous methods.
The hybrid algorithm has the advantages from both genetic algorithm and tabu search algorithm. It makes use of the advantage of multiple search points in genetic algorithm, and can overcome poor hill-climbing capability in the conventional genetic algorithm by using the flexible memory functions of TS. Compared with some previous algorithms, GATS algorithm has better performance in global optimization and can predict 3D protein structure more effectively.
蛋白质结构预测（PSP）在不同领域有着重要应用，如药物设计、疾病预测等。在蛋白质结构预测中，有两个重要问题。第一个是结构模型的设计，第二个是优化技术的设计。由于现实蛋白质结构的复杂性，本文采用的结构模型是一个简化模型，即非晶格AB模型。在假设结构模型之后，需要优化技术来基于假设的结构模型搜索蛋白质序列的最佳构象。然而，即使假设最简单的模型，PSP也是一个NP难问题。因此，已经开发了许多算法来解决全局优化问题。本文开发了一种将遗传算法（GA）和禁忌搜索（TS）算法相结合的混合算法来完成这项任务。
为了开发一种高效的优化算法，针对所提出的遗传禁忌搜索算法开发了几种改进策略。这些策略的联合使用可以提高算法的效率。在这些策略中，引入交叉和变异算子的禁忌搜索可以提高局部搜索能力，采用可变种群大小策略可以保持种群的多样性，排名选择策略可以提高低能量值个体进入下一代的可能性。使用斐波那契序列和真实蛋白质序列进行了实验。实验结果表明，所提出的GATS算法获得的最低能量低于以前的方法。
该混合算法具有遗传算法和禁忌搜索算法两者的优点。它利用了遗传算法中多个搜索点的优势，并且可以通过使用TS的灵活记忆功能克服传统遗传算法中爬山能力差的问题。与一些以前的算法相比，GATS算法在全局优化方面具有更好的性能，并且可以更有效地预测3D蛋白质结构。
