求解蛋白质折叠问题的模拟退火算法

《求解蛋白质折叠问题的模拟退火算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、小型微型计算机系统2007年1月第1期JournalofChineseComputerSystemsVol.28No.12007求解蛋白质折叠问题的模拟退火算法陈矛,黄文奇,吕志鹏(华中科技大学计算机学院,湖北武汉430074)E-mail:mchen_1@163.com摘要:通过构造新的数学模型,把三维AB模型的蛋白质折叠问题由一个带约束的优化问题转化为无约束优化问题,然后提出一个模拟退火算法.对如何得到初始构形,提出了一个启发式策略.实算结果表明,本文算法效率较高,对四条氨基酸测试序列,本文算法得到的

2、最低能量都要优于nPERM算法得到的结果.关键词:蛋白质折叠问题;AB非格点模型;NP难度中图分类号:TP393文献标识码:A文章编号:1000-1220(2007)01-0075-04SimulatedAnnealingAlgorithmforProteinFoldingProblemCHENMao,HUANGWen-qi,LvZhi-peng(SchoolofComputerScience,HuazhongUniversityofScienceandTechnology,Wuhan430074,Chi

3、na)Abstract:Byconstructinganewmathematicmodel,theproteinfoldingproblemofthree-dimensionalABmodelisconvertedfromanonlinearconstraint-satisfiedproblemtoanunconstrainedoptimizationproblem.Asimulatedannealingalgorithmisproposedforsolvingthisunconstrainedoptim

4、izationproblemandaneffectiveheuristicstrategyisintroducedforgeneratingbet-terinitialconfiguration.ThecomputationalresultsshowthatouralgorithmcanoutperformnPERMalgorithmintermsoffind-ingstateswithlowerenergyforthefourbenchmarksequences.Keywords:proteinfold

5、ing;ABoff-latticemodel;NPhard1引言的氨基酸链的能量U1为:n-1n-2n蛋白质折叠问题,即蛋白质结构预测问题,是生物信息学U1=∑V1(Hi)+∑∑V2(rij,Fi,Fj)(1)i=2i=1j=i+2领域的核心问题之一.蛋白质所具有的生物学功能在很大程其中度上取决于蛋白质的空间结构,因此了解蛋白质的空间结构1在生物学领域具有重要意义.近年来,Anfinsen及Dill等V1(Hi)=(1-cosHi)(2)4[1,2]人的研究表明,根据蛋白质的氨基酸序列和能量模型,利-12

6、-6V2(rij,Ni,Nj)=4[rij-C(Fi,Fj)rij](3)用理论计算的方法来对蛋白质结构进行预测是一个可行的方rij是链上不相邻两单体之间的距离(i

7、函数简单,只考虑空间上相邻的强相互吸引,B-B单体之间的弱相互吸引以及A-B单体之[4]间的弱相互排斥是一致的.的H单体之间的相互作用.1995年,Stillinger等提出了一种被称为AB模型的非格点模型.AB模型不仅考虑了空间上虽然AB模型是一个简化模型,但对该模型的求解依然是困难的.该问题已被证明是NP完全问题,这意味着不存在相邻单体之间的相互作用对蛋白质结构的影响,还考虑了不[5]相邻单体之间的“非局部”作用的影响,因而比HP模型更接既完整严格又不是太慢的求解算法,因此,人们提出一些启发式或近似算

8、法来求解.近真实的蛋白质折叠问题.[4]与HP模型相似,AB模型只考虑疏水氨基酸(A)和亲水对AB模型的蛋白质折叠问题,目前有神经网络,蒙特卡罗[6]和分子动力学[7]以及nPERM[8]等多种算法.这些算法氨基酸(B)这两类单体.AB模型中,链上相邻单体之间的距离为1,不相邻单体之间具有Lennard-Jones形式的引力势能.在求解AB模型的蛋白质结构预测问题时取得了一些进展,另外,连续两个键之间也会产生弯曲势能.因此,一