基于改进遗传算法的蛋白质三维折叠模拟

基于改良遗传算法的蛋白质三维折叠模拟【摘要】根据氨基酸的序列预测蛋白质的空间构造在基因治疗药物分子设计等方面有宏大的潜在应用价值。本研究基于hp格子模型利用改良的遗传算法预测了蛋白质的三维空间构造。改良的遗传算法引入了克隆体数量限制策略、巢穴竞争选择策略及部分优化策略等。实验结果说明，改良的遗传算法显著地进步了蛋白质构造的预测效率，模拟的蛋白质构造紧凑，更接近真实蛋白质的构型。【关键词】遗传算法蛋白质折叠三维hp模型1引言蛋白质是生命活动的重要承当者，蛋白质所具有的功能在很大程度上取决于其空间构造，掌握蛋白质的空间构造在基因治疗和药物分子设计方面有极大的潜在应用价值[1]。目前,测定蛋白质空间构造的方法主要是核磁共振和x射线衍射技术，这些技术消耗宏大，测定效率低下，远远满足不了日益增加的待测定海量蛋白质的需要[2]。根据氨基酸的序列,从理论上预测蛋白质的空间构造有助于进步测定蛋白质构造的效率，对生物医学的开展有重要的意义[3]。蛋白质构造预测是个典型的“np问题〞〔算法的复杂性随着规模的增长成指数增长〕，也就是蛋白质的构造不能用一个多项式来明确表示，其能量的最小值必须通过启发式算法来搜索[4]。目前开展的启发式算法主要有蒙特卡罗模拟算法、禁忌算法、蚁群算法、链增长算法、模拟退火算法和遗传算法等[5～8]。其中遗传算法由于高效地搜索效率得到了广泛的应用。本研究针对hp模型〔疏水性和亲水性格子模型〕采用改良遗传算法模拟了蛋白质的三维空间折叠行为，改良的遗传算法主要引入了克隆体数量限制策略、巢穴竞争选择策略和部分优化策略等。2原理和方法2.13dhp模型最简单的蛋白质分子模型是hp格子模型，该模型把所有的氨基酸残基按疏水性和亲水性分成两类：疏水性残基〔h〕和亲水性残基〔p〕。因此，蛋白质序列被抽象为一个由h和p组成的序列[9]。hp格子模型在三维空间中的折叠简称3dhp模型，每个残基的折叠方向可以向左、向右、向上、向下90°或者向前,折叠的残基不能重叠在其它残基上，整个蛋白质序列在一个三维方格上折叠。3dhp模型的理论根底是氨基酸的疏水性是球蛋白形成的主要驱动力[2]。该模型忽略了侧链的影响，符合真实蛋白的根本特征。疏水性的氨基酸为了减小与水分子的接触面积而彼此靠近并进入分子的内部，形成了疏水互相作用；亲水性氨基酸那么形成了分子的外表，形成严密的团状构象。3dhp模型虽然过于粗糙，与真实蛋白分子相差甚远，但是它能模拟真实蛋白的折叠行为，且计算简单，有利于比照不同折叠搜索算法。hp格子模型中，一个构象的能量计算规那么如下：当两个在序列上不相邻的节点在空间上相邻时，便提供应构象一个互相作用能量.对于一个特定的序列构造，它的总能量e为：ｅ＝∑i＜n,j＜ni=1,j=i+1δreij，式中n为蛋白质序列的长度。假如i与j在空间中拓扑相邻但序列不相邻，那么δr等于1，否那么等于0。eij表示在序列中第i个氨基酸与第j个氨基酸之间的能量。三维空间中拓扑相邻的残基有３种情形：hh、hp、pp，３种拓扑关系的能量规定如下[5]：ｅｈｈ＝－１．０，ｅｈｐ＝０．０，ｅｐｐ＝０．０〔1〕由此，蛋白质三维折叠模拟的命题表述为：搜索蛋白质序列在空间中的构造，使该构造中拓扑相邻的hh数量最多。上述的模型得到了广泛的应用，然而这种模型只考虑hh间的互相作用，而未考虑hp间的互相作用。实际的蛋白质构造是亲水性残基包裹疏水性残基形成球状构造，忽略hp间的互相作用将导致虽然找到了最多的hh接触数量，但是末端的疏水性分子p没有任何约束而随意折叠，蛋白质空间构造的自由度太大，甚至形成与真实蛋白质构造相差太远的构造。实际３种拓扑关系的能量大小关系为：ｅｈｈ＜ｅｈｐ＜ｅｐｐ，本研究对３种拓扑关系做如下修正：ｅｈｈ＝１．０，ｅｈｐ＝－０．４，ｅｐｐ＝０．０〔2〕这种修正考虑了氨基酸残基应满足的物理制约条件，不同类型的氨基酸残基趋向于别离，满足关系式[1１]：２ｅηρ＞ｅηη＋ｅｐｐ〔３〕本研究中，个体适应度规定为：ｆi＝－ei＋０．０１〔4〕分析化学第37卷第1期李绍新等：基于改良遗传算法的蛋白质三维折叠模拟该规定保证了适应度总为正数，个体能量越低，适应度越大。增加的常量〔0.01〕保证了个别个体能量为零时适应度不为零，也有时机参与遗传操作。修正后的蛋白质三维折叠模拟命题表述为：寻求给定蛋白质序列具有最大适应度的三维空间构造。2.2遗传算法遗传算法首先是由美国的hlland教授提出来的启发式优化组合方法[1２]。它基于达尔文进化论和孟德尔遗传学说，仿效生物的进化与遗传，根据“生存竞争〞和“优胜劣汰〞的原那么，借助复制、交换、突变等操作，使所要解决的问题从初始解一步步逼近最优解。与其他搜索方法相比，ga具有随机性、鲁棒性、并行性、全局搜索等优越性[1３]。遗传算法运行时首先编码建立解的初始群体，编码一般采用二进制或浮点，每个解用特定的基因串表示，突变算子独立作用在串上，在最初的方案中，突变算子就是改变串上的一个位。在执行完一定数量的突变后，由穿插操作产生新的串：选择集团中的两个串，并确定串中的断点，两个新的集团成员由一个串的左边部分连接到另一个串的右边而形成。这样的操作进展到一个由可承受串组成的新的群体形成为止。接着进展下一阶段的循环。这个步骤重复进展直到集团收敛于一个串，适应值函数那么用来评估突变和穿插所产生新串的质量。〔１〕随机产生初始群体，计算每个个体的适应度；〔２〕生存选择：根据个体适应度大小选择生存个体，一般采用轮盘赌选择，适应度越大的个体被选中的概率越大；〔３〕穿插：采用单点或两点穿插。根据穿插概率随机选择一对穿插个体，在选中的个体上随机选择穿插位点，形成两个新个体；〔４〕变异：根据变异概率随机选择变异位点施行基因突变，一般采用均匀变异；〔５〕适应度评价：根据能量法那么计算每个个体的适应度大小；〔６〕群体更新：假如子代个体中最优个体的适应度大于父代最优个体，那么保存子代的最优个体，通过遗传操作后的所有个体代替父代个体，重复步骤2～6直到产生满足要求的最优个体。〔ⅰ〕按公式〔４〕计算适应度，该计算方法可以保证所有个体都有时机参与遗传操作；当群体中出现无效个体〔几个氨基酸残基重叠在同一位置〕，对该个体给予惩罚扣分，不是简单的丢弃该个体；〔ⅱ〕生存选择阶段引进克隆体数量限制策略。在用轮盘赌选择个体时候，个别个体的竞争力很强，会被大量的繁殖，群体逐渐同质化。该策略限制了在进化中个别个体被克隆的数量，保持了群体的多样性，防止群体的早熟收敛；〔ⅲ〕穿插阶段引进多点穿插，巢穴竞争选择策略。一般的进化算法是两个亲代个体穿插后产生两个子代个体。巢穴选择策略是两个亲代个体杂交后产生多个子代个体，子代个体与亲代个体竞争选择最好的两个个体遗传进化。根据氨基酸的长度，采取3点穿插，每对随机选择的亲代个体随机穿插2次产生4个后代个体；〔ⅳ〕部分优化策略。当算法搜索到一定阶段后，染色体进化速度骤然降低，最优个体往往停顿进化。因此，对最优个体进展部分优化有利于算法跳出‘部分陷阱’。部分优化策略操作如下：首先选择群体中最优个体；再从第二个位开场，对最优个体进展随机变异操作；再计算变异个体的适应度。假如变异后个体的适应度f2大于等于变异前的适应度f1，承受变异后的新个体，最后对新个体的下一位继续进展变异操作，重复步骤〔ⅲ〕和〔ⅳ〕直到个体的所有位变异操作完毕。3结果与讨论３．１改良的遗传算法的性能比拟利用改良的遗传算法对含27个残基的标准hp序列进展了三维折叠模拟，序列如表1所示。该序列在许多文献中屡次应用[1４～1６]。程序采用atlab语言编写，优化后的参数为群体规模200，穿插概率0.75，变异概率0.05。对每个序列折叠模拟20次。实验结果发现，改良后的算法性能得到了显著的进步，不仅能以较小的代价搜索到最低能量构型，而且搜索到的构型紧凑，更接近真实蛋白的构造。表1测试的蛋白质序列〔略〕table1peptidelengthtestases为了便于比拟，对最后搜索到的最优个体采用公式〔1〕重新计算能量。表2是改良算法后的结果与其它标准算法结果比拟。由２表可以看出，搜索到最低能量时，unger需要的能量评价函数较多，pattn需要的能量评价函数大为减少，本研究需要的函数评价数目比pattn算法有所减少，但是个别序列有所增多。表2测试能量评价数结果比拟〔略〕table2resultparisnfenergyevaluatinunger采用的遗传算法在初始阶段所有个体从一条直线开场变异[15]，变异后的个体用蒙特卡罗方法过滤。在穿插阶段算法实行单点穿插，穿插后的个体也用蒙特卡罗方法过滤。当产生的后代个体出现无效个体时抛弃该个体，重新产生新的个体。这种算法类似于模拟退火算法，抑制了遗传算法的搜索性能，所以该算法的能量评价数目非常多。pattn的遗传算法采用相对编码，两点穿插，当出现无效个体时候，对每个重叠位置采取惩罚性扣分[1４]。pattn的算法性能得到了较大的进步，但是pattn的格子模型没有考虑hp的互相作用。3.2改良策略的影响本研究中的克隆体数量限制策略对维持种群的多样性起了很重要的作用。实验发现，当群体遗传一定代数后，群体进化陷入停滞，群体中的个别个体大量繁殖，甚至占了近群体20%～50%，这样的群体很难有新的进化。采用克隆体数量限制策略有效地解决了过度繁殖的问题，该策略规定群体中一样个体不能超过一定数量，超过的部分用随机产生新的个体来代替。该策略不必频繁使用，每遗传10代使用一次比拟节约资源。实验发现克隆体限制数量设定为3～6比拟适宜，本研究将克隆体数量限定为4。本研究中的多点穿插策略也有利于保持个体的有效性。对于一个染色体，改变其中一个氨基酸的折叠方向将对整个个体产生宏大的影响，而多点交换策略只改变其中一段染色体的构造，降低了单点穿插带来的压力。巢穴竞争选择策略使得新的个体不仅面临与同辈个体间的竞争，也面临与父辈个体的竞争，进步了繁殖优秀个体的才能。本研究采用的部分优化策略是系统变异，类似于ntearl搜索方法[17]。本策略对最优染色体进展二次寻优，在算法的初期阶段爬山才能较强，但是在后期根本上失去了对染色体的改造才能，产生有效个体数不多。3.3改良能量关系的影响本研究的适应度的规定与其它文献有所差异[5,7,9]，一般的适应度都是直接用hh间的接触数量表示适应度的上下，没有hh接触的个体适应度为0，没有时机参与遗传，这种个体中也存在优秀基因。本实验增加了一个常量0.01，个体适应度都不为零，所有的个体都有被选中的时机，这种策略不仅保持了群体的多样性，也使更多的优秀基因有时机参与遗传。图1序列27.０9的两种不同构造〔a〕为未改良算法得到的构造，〔b〕为改良算法后的构造，两种构造的hh键数量都是7，图中黑球表示非极性分子h，白球表示极性分子p〔略〕图2序列p8h8p8的两种不同构造a为未改良算法得到的构造，b为改良算法后的构造，两种构造的hh键数量都是5，图中黑球表示非极性分子h，白球表示极性分子p〔略〕结果说明，改良的遗传算法维持了种群的多样性，增强了算法寻优才能，进步了搜索效率，模拟的蛋白质构造紧凑，更接近真实蛋白质的构型。【参考文献】1bakerdsalia.siene,2001,294(5540):93～962anfinsen．siene,1973,181(96):223～2303hrist,alenas,hlgerhh.bbiinfratis,2022,8:342～3624harte,istrails.jurnalfputatinalbilgy,1997,4(1):1～226