一种禁忌搜索算法在二维HP非格模型中的应用  

A tabu search and its application in 2D HP off-lattice model

作　　者：岳晓晖[1] 唐焕文[1] 郭崇慧[1] 

机构地区：[1]大连理工大学应用数学系,辽宁大连116023

出　　处：《计算机与应用化学》2005年第12期1101-1105,共5页Computers and Applied Chemistry

基　　金：国家自然科学基金资助项目(90103033)

摘　　要：禁忌搜索算法是一种启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题,本文探讨将一种记忆的禁忌搜索算法应用于求解蛋白质结构预测问题。文中首先介绍了一种二维HP非格模型,此模型最后可以归结为一个全局优化问题,然后介绍了记忆的禁忌搜索算法在其中的应用,通过与PERM(Pruned-Enriched-Rosenbluth Method) 比较,发现禁忌算法能得到较好的实验结果,经分析发现虽然二维HP非格模型很简单,但却能反映蛋白质结构的一些简单的性质,即在蛋白质结构中,疏水性氨基酸形成束,总是被极性氨基酸包围。数值实验表明该算法对于蛋白质结构预测是可行有效的。Tabu search algorithm is a class of heuristic global optimization algorithms which has been successfully applied to many combination optimization problems. In this paper, a memory Tabu search algorithm is applied to solve 2D HP off-lattice model of protein structure prediction problems. The performance of our algorithm is comparable to PERM algorithm. The model is simple and reflects the simple property of protein structure. The hydrophobic monomers form clusters of typically 4 - 5 particles and they are always flanked by polar monomers along the chain. Numerical tests illustrate that the memory Tabu search algorithm is feasible and effective to protein structure prediction problems.

关 键 词：蛋白质结构预测 二维HP非格模型 禁忌搜索算法 

分 类 号：Q71[生物学—分子生物学] O224[理学—运筹学与控制论]