（应用数学专业论文）新蒙特卡罗方法在蛋白质折叠模拟上的应用.pdf

上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 摘要 蛋白质折叠和结构预测是生物信息学研究中最富有挑战性的研究领域，对于 人们进一步了解蛋白质的结构和功能具有非常重要的意义。蛋白质折叠的计算机 模拟和预测作为一种辅助手段，可直接应用于新的功能蛋白质的设计和研究。正 是由于理论和应用方面的重要性，使得该领域的研究工作越来越受到重视。 随着各种随机算法的兴起并应用到各个领域，人们发现随机算法对于解决蛋 白质折叠问题有其特有的优点。特别是蒙特卡罗方法由于它本身的优点( 方法不 受解空间结构和分布的影响) 渐渐引起了人们的兴趣。各种改进的蒙特卡罗方法 成为计算机模拟蛋白质折叠的重要工具。 本文将并行回火与遗传算法的混合算法、群体模拟退火方法以及群体模拟退 火方法与遗传算法的混合算法这三种改进的蒙特卡罗方法应用到蛋白质折叠模 拟计算上，并就二维网格模型比较了这三种方法搜索最小能量构象的能力以及计 算了这三种方法得到最小能量构象所花费的时间。接着本文使用我们提出的群体 模拟退火方法与遗传算法的混合算法模拟计算了三维空间中的蛋白质折叠。本文 又使用该方法模拟计算了p d b 数据库中的三条氨基酸序列，比较了采用不同适应 值函数的模拟计算结果并将结果与p b b 数据库中的蛋白质结构进行比较。本文最 后讨论y - 维空间中蛋白质残基的单突变与双突变，再次验证了有关蛋白质突变 的一些特点。 关键词： 蒙特卡罗方法蛋白质折叠蛋白质残基突变 上海大学硕二l 学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 a b s t r a c t t h ep r e d i c t i o no fp r o t e i nf o l d i n ga n dp r o t e i ns t r u c t u r e i so n eo ft h em o s t c h a l l e n g i n g r e s e a r c h e s i nb i o i n f o r m a t i c sa n di s v e r yi m p o r t a n t f o rf a r t h e r u n d e r s t a n d i n go fp r o t e i ns t r u c t u r ea n dp r o t e i nf u n c t i o n a sa na c c e s s o r i a lm e t h o d ， c o m p u t e rs i m u l a t i o nc o u l d b e d i r e c t l ya p p l i e d t op r o t e i nd e s i g na n dr e s e a r c h b e c a u s e o ft h e i m p o r t a n c e o ft h e o r ya n da p p l i c a t i o n ，t h i sw o r ki s p a i d m o r ea n dm o r e a t t e n t i o n h e nm o r ea n dm o r es t o c h a s t i c a l g o r i t h m sb e i n ga p p l i e d ，t h e i rs p e c i a l a d v a n t a g e s o n s o l v i n gp r o t e i nf o l d i n ga r ea l s od i s c o v e r e d e s p e c i a l l yt h em cm e t h o d ， w h i c hd o e s n tb ei n f l u e n c e d b ys t r u c t u r e a n dd i s t r i b u t i o no fs o l u t i o n s p a c e ，i s a t t r a c t i n gg r o w i n gi n t e r e s tf r o mp e o p l e al o to fn e wm c m e t h o d sa r eb e c o m i n gt h e m a i nt o o l so f p r o t e i nf o l d i n gs i m u l a t i o n s t h i s p a p e rm a i n l yd e a l sw i t ht h r e en e wm o n t ec a r l om e t h o d s ，n a m e l y , am i x t u r e o f p a r a l l e lt e m p e r i n ga n dg e n e t i ca l g o r i t h m ，p o p u l m i o n o r i e n t e ds i m u l a t e da n n e a l i n g a sw e l la sam i x t u r e o f p o p u l a t i o n o r i e n t e ds i m u l a t e da n n e a l i n ga n dg e n e t i ca l g o r i t h m ， w h i c ha r ea p p l i e dt ot w od i m e n s i o n a ll a t t i c em o d e lf o r p r o t e i nf o l d i n g ，t h ea b i l i t yt o f i n dt h el o w e s t e n e r g y c o n f o r m a t i o na n d c o m p u t a t i o n a l c o s ta r e c o m p a r e d m e a n w h i l e ，am i x t u r eo fp o p u l a t i o n o r i e n t e ds i m u l a t e d a n n e a l i n g a n d g e n e t i c a l g o r i t h m i s a p p l i e dt o t h r e ed i m e n s i o n a ll a t t i c em o d e lf o rp r o t e i n f o l d i n g t h i s m e t h o di sa l s o a p p l i e d t oc a l c u l a t et h r e ea m i n oa c i d s e q u e n c e sf r o mp d ba n d c o m p a r e t h er e s u l t sb yd i f f e r e n tf i t n e s sf u n c t i o n sa n dt h er e a ls t r u c t u r e sf r o mp d b a t l a s tt h i s p a p e r d i s c u s s e s t h e s i n g l e m u t a t i o na n dd o u b l em u t a t i o nt o p r o v e c h a r a c t e r i s t i c s o f p r o t e i nm u t a t i o n k e y w o r d s ： m cm e t h o d p r o t e i nf o l d i n g m u t a t i o n 上海大学 本论文经答辩委员会全体委员审查，确认符合上 海大学硕士学位论文质量要求。 答辩委员会签名：( 工作单位职称) 主任： 委 导 答辩日期： 勰鼯渤鬣黪 l 0 ( z 躺勰 多一亡文0 岳 蜘航姘桐 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 期型岬 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 盂查导师签名：日期： 本文的研究工作受上海市重点学 科建设项目及国家8 6 3 高技术研究发展计划 项目( 2 0 0 2 m 1 2 3 4 0 2 1 ) 资助。 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 第一章蛋白质折叠 1 1 蛋白质折叠结构预测的研究意义 蛋白质工程是现代生物技术发展的前沿领域，其根本目的是要将天然存在的 蛋白质按照人们的设想进行改造，或者根据需要设计出具有某种特殊功能的非天 然的新的蛋白质，而这种改造和设计的重要基础之一就是蛋白质折叠结构的预 测。蛋白质折叠结构的形状在很大程度上决定了其可能具有的生物功能。也就是 说，蛋白质的结构与功能之间具有一致性，有什么样的结构必定有什么样的功能， 反之亦然。因此，对蛋白质折叠结构的预测和研究在蛋白质工程中有着极其重要 的地位。 1 9 6 1 年，a n f i n s e n 等在实验的基础上提出某些蛋白质在体外的一定条件下 解聚失活后可以自动折叠而恢复其原有高级结构与活性的著名论断，这也就意味 着蛋白质的氨基酸序列及环境决定其三维构象，这就是进行蛋白质结构预测的理 论基础。截止至2 0 0 4 年2 月1 5 日，s w i s sp r o t 4 2 1 1 版公布的已知氨基酸序列的 蛋白质分子为1 4 4 7 3 1 个( 共由5 3 6 8 3 2 3 9 个氨基酸残基组成，平均每条序列由 3 7 0 个氨基酸残基组成) ，但是同年2 月2 4 日p d b 数据库中收录的蛋白质结构 只有2 4 4 4 4 个，结构和序列的比例大约是l 比6 。显然蛋白质分子三维结构测定 的速度仍远远落后于其氨基酸序列测定的速度。所以，根据蛋白质的氨基酸序列 预测其相应的空间结构就成为生物信息学研究中一个最重要的、迄今仍未完全解 决的问题。 1 2 蛋白质结构i 蛋白质是一种由2 0 种l 型a 氨基酸，通过口碳原子上的取代基间形成的酰 胺键连成的，具有特定空间构象和生物功能的肽链构成的生物大分子，图卜l 是酪胺酸激胸的图形。氨基酸为两性分子，因分子侧 链的不同性质，而有酸性、碱性、极化中性( 亲水性) 和非极化中性( 疏水性) 四类氨基酸之别。构成蛋白 质的2 0 种氨基酸其侧链在大小、形状、电荷、形成 氢键的能力和化学活性方面都存在差异。蛋白质实现 的功能范围之所以如此广泛，就是由于这2 0 种氨基 酸的差异以及它们的各种组合的变化的结果。这2 0 。摘自黑基慧黧i 晦d i n ) 种氨基酸不仅是蛋白质的最基本组成，也是分析蛋白 质肽链一级结构的基本单位，它们的名称和简写见表 l l ，基本性质详见参考文献 1 。 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 表卜1 氨基酸名称以及3 字母、1 字母符号 名称三字粥单字嘴 名称三字粥学社粥号 丙蟹嗷( a a n i n e ) a l aa赛自骏( 1 e l d 鼍) l e ul 精蟹嗷( m 3 i - 她)蜘 r j 氯酸( 畸怕)蝻 k 无漱妇闷呻e ) a n甲嶷目眩( m 酣自啪1 e ) m e tm 天冬复暧( a t g ：t 列c a d d )衄 d 苯穗| 嗷( p h 晰怕： p h ef 半噱瞰( q 哦蚰)c y s c脯女嗷( 胁)p r op 谷醐按( g i 扫n 亩e ) g ho 丝睦酸值打侍) s 可s 徽皤捃n i c 到) g be 苏l 啜( 廿旧| b ) 1 1 tt 甘日骏( g 怕)g g篚暧啦科栅) t r p w 组翱睃( h i s 6 d r m )h sh 懒蛳隋)可 y 异 馥嗷国d | e 曲e )i b l缬孤竣m )v a l v 氨基酸与氨基酸之间通过缩水而形成肽键，进而形成多肽链。通常的多肽链 约为1 0 0 1 5 0 0 个氨基酸。蛋白质的一级结构指多肽链中氨基酸残基的排列顺序， 靠共价键维持多肽链的连接，而不涉及其空间排列，是一个无空间概念的一维结 构；蛋白质的二级结构指多肽链骨架的局部空间结构，不考虑侧链的构象及整个 肽链的空间排列，有时也可以认为，蛋白质的二级结构是构成蛋白质的三级结构 的部件；蛋白质的三级结构则是指整个肽链的折叠情况，包括侧链的排列，也就 是蛋白质分子的空间结构或三维结构。在此基础上人们又提出了蛋白质超二级结 构、结构域、四级结构的概念。 一般来说，在给定蛋白质序列后，首先进行蛋白质序列对比，在已知蛋白质 序列库中寻找同源蛋白质。如果找到同源蛋白质，并且该蛋白质的结构已经确定， 那么就可以利用同源信息建立目标蛋白质的结构。如果没有同源蛋白质的结构， 一般的做法是先预测二级结构再进行三级结构的预测。但是该方法的准确性依赖 二级结构的预测结果，由于目前仍然没有很精确的二级结构的预测方法，所以这 样的预测往往不能得到较令人满意的结果。现在比较多的做法是不依赖二级结构 的预测，根据蛋白质序列判断其折叠模式，进而预测三级结构。 1 3 蛋白质结构预测方法川1 2 l 由于人们越来越认识到研究蛋白质结构的重要性，越来越多的方法被用来研 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 究蛋白质结构，下图1 - 2 对一些主要的方法做个简单的小结。 研究7 珐 理硷万皓 珐k 溅鬈准 扶曼预测毪 比较建摸琏 辰向钎叠涟 确定性茸皓巨：i ；i f 遗传笪毪 随帆茸 圭j 萤件卡穸7 皓 i 模拟遮太方选 图卜2 各种蛋白质结构预测方法 下面简单介绍一下各种方法。 在各种实验方法之中，x 射线晶体学和多维核磁共振方法是目前比较有效的 蛋白质结构测定方法。利用x 射线晶体学方法测定蛋白质分子的构象，结果比 较可靠，它可以达到其它方法达不到的精度。但是，与溶液中的构象相比，蛋白 质分子在晶体中的构象是静态的，所以，利用蛋白质晶体不能测定不稳定的过渡 态的构象。而且，很多蛋白质很难结晶，或者很难得到用于结构分析的足够大的 单晶。另外，该方法的工作流程较长。核磁共振是指核磁矩不为零的核，在外磁 场的作用下，核自旋能级发生塞曼分裂( z e e m r r ls p l i t t i n g ) ，共振吸收某一特定 频率的射频( r a d i of r e q u e n c y , r f ) 辐射的物理过程。近年来，多维核磁共振方法 测定小蛋白的三维结构得到了成功的应用。该方法不需要制备蛋白质晶体，但这 种方法仅限于分析长度不超过1 5 0 个氨基酸残基的小蛋白，并且对样品的需要量 大、纯度要求高，且蛋白质结构中不能有很多重复单元。随着已知结构的蛋白质 数量和已知序列的蛋白质数量的差距越来越大，如何用理论的方法来进行蛋白质 结构预测已经成了生物信息学研究中的一尊圣杯。 蛋白质结构预测的理论方法总体上可分为三大类，即比较建模法 ( c o m p a r a t i v e m o d e l i n g m e t h o d ) 、反向折叠法( i n v e r s e f o l d i n g ) 和从头预测法( a b i n i t i op r e d i c t i o nm e t h o d ) 。近年来，比较建模法和反向折叠法的研究都已取得重 要的进展，一些商品化计算机软件已投入使用，并不断被改进，如c o m p o s e r 和 t h r e a d i n g 等。 比较建模法是基于知识的蛋白质结构预测方法，又称为同源结构预测，它是 在未知蛋白质中有同源结构可以参考的情况下应用的一种技术，是目前最为成熟 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 的预测方法。按照目前的定义，若目标蛋白质序列与模板序列经对比后的序列相 似性在4 0 ( 也有人认为在3 5 ) 以上，则它们可能是同源蛋白，可以用同源蛋 白模型构建的方法预测其三维结构。因为它们可能是由同一种蛋白质分化而来， 它们具有相似的空间结构，相同或相近的功能。因此，若知道了同源蛋白家族中 某些蛋白质的结构，就可以预测其它一些序列已知而结构未知的同源蛋白的结 构，可以用同源模型构建的方法预测未知蛋白质的三维结构。比较建模法共分六 个主要步骤；目标蛋白序列与模板序列的匹配、确定蛋白质的结构保守区、保守 区的主链模建、结构变异区的主链建模、侧链的安装和优化以及对建模结构的优 化和评估。 反向折叠法是近年来发展起来的一种比较新的方法。它可以应用到没有同源 结构的情况中，且不需要预n - 级结构，即直接预测三级结构，从而可以绕过现 阶段二级结构预测准确率低的缺点，是一种很有潜力的预测方法。反向折叠法的 主要原理是把目标蛋白的序列和已知的结构进行匹配，找出一种或几种匹配最好 的结构作为目标蛋白质的预测结构。它的实现过程是总结出己知的独立的蛋白质 结构模式作为目标结构进行匹配的模板，然后用经过对现有的数据库的学习总结 出的可以区分正误结构的平均势函数作为判别标准来选择出最佳的匹配方式。 比较建模法和反向折叠法这两类方法的缺点是在预测目标蛋白质的结构时 都要利用已知的结构数据库，当目标蛋白质找不到同源蛋白质，或相似性过低时 这些方法都无法奏效。相比较而言，从头预测法仅利用氨基酸序列所具有的信息 来预测目标蛋白质的空间结构，因此具有更大的挑战性。从头预测方法又可以细 分为预测二级结构、预测超二级结构、预测结构类型、预测折叠模式以及预测三 级结构。本论文主要讨论蛋白质折叠结构的预测，即主要考虑蛋白质主链的折叠 构象，不考虑侧链的结构或者考虑简化了的侧链结构。关于从头预测方法的内容， 我们将在介绍了有关蛋白质折叠的概念以后再来叙述。 1 4 蛋白质折叠 蛋白质的结构层次是怎么产生的呢? 简单地说是肽链折叠的结果。一条伸展 的多肽链为什么能折叠成具有特定空间构象的蛋白质呢? 这是2 0 世纪6 0 年代以 来，蛋白质研究中一个重要的课题。早在3 0 年代我国科学家吴宪就提出了蛋白质 的变性理论，约在同一时期，英国剑桥大学的b e m a l 也曾指出蛋白质折叠是一个 物理过程，而且能在试管中进行实验。再后来a n f i n s e n 等提出了蛋白质序列与结 构之间关系的原理。应该说是直n 9 0 年代人们才在这方面有了全面的认识和重要 的进展i j j 。 蛋白质折叠包含两个方面内容：变性的蛋白质或多肽链的折叠以及通过三联 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 密码翻译成的氨基酸序列链( 新生肽链) 的折叠。因为蛋白质折叠是一个十分复 杂的问题，既有热力学控制又有动力学控制，为简单起见一般我们只关心第一个 方面( 因为第二个方面更为复杂) 。因此，我们通常说的蛋白质折叠问题就是指 第一个方面的研究。 根据a n f m s e n 等提出来的经典的“热力学假说”，认为天然蛋白质多肽链采 取的构象是在一定环境条件下热力学上最稳定的结果，采取天然构象的多肽链和 它所处的一定环境条件( 如溶液成分、p h 、温度、离子强度等) 构成的整个系统 的总自由能最低。所以处于变性状态的多肽链在一定的环境条件下能够自发折叠 成天然构象。肽链中的单键处于不同的运动状态，使肽链骨架中的酰胺和残基侧 链基团能彼此接触并进一步相互作用，这样一来使得某些构象的能量低于松散的 肽链，这些构象就相对稳定下来。 但是，有一个反对热力学可行性的假设，叫做“l e v i n t h a l 矛盾”。它指出， 因为蛋白质有许多可能的构象，所以如果蛋白质在整个构象空间进行搜索，它的 折叠过程可能要花费几年甚至更长的时间。但是，许多蛋白质的折叠是在毫秒时 间里完成的，这就说明蛋白质不可能在所有的构琢中寻找能量最小值。l e v i n t h a | 提出蛋自质折叠也许是沿着某一特定的折叠路径( f o i d i n gp a t h w a y ) 进行的， l e v i n t h a l 的理论导致人们寻求蛋白质折叠的路径。 研究表明，蛋白质折叠是个既涉及热力学控制又涉及动力学控制的问题。 热力学控制指的是：自然结构仅由最后的自然条件确定而不是由初始的变性条件 确定，折叠与路径无关。在单纯的热力学控制下，蛋白质折叠需要很长的时间。 动力学控制指的是：折叠是在具有生物学时间尺度内快速完成的，这是由于折叠 是与路径有关的，最后的结构也许是不同的并依赖于折叠开始时的变性条件。人 们现在已分离到一些能在动力学上促进多肽链正确折叠的辅助因子。 总的来说，蛋白质的折叠是遵循“热力学假说”的，从能量高的状态向能量 低的状态转变，但在这个过程中会受到动力学上的控制。热力学控制与动力学控 制在蛋白质多肽链的折叠反应中是统一的，尽管不同的蛋白质在其折叠过程中所 体现出来的二者所起作用的大小可能有所不同。对一些小分予单结构域的蛋白质 来说，折叠过程比较简单，在热力学控制下较易完成；而一些结构较复杂的蛋白 质特别是一些在折叠时需要二硫键重排，脯氨酰顺反异构化的蛋白质在折叠过程 中从总体上是受热力学控制，但折叠途径更受动力学控制【4 1 。 根据分子生物学中心法则，生物遗传信息的传递是由d n a 到r n a ( 转录) 、 r n a 到蛋白质多肽链( 翻译) 、再由多肽链形成具有生物活性的蛋白质( 折叠) 进行的。目前对前两个过程已有相当深入和清晰的了解，但对后者尚不十分清楚。 可以说蛋白质折叠是生物学中心法则中至今尚未完全解决的一个重大生物学问 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的戍用 题。在解决蛋白质折叠问题的各种方法中，x 射线晶体 ； 亍射方法以及多维核磁共 振方法较为有效。第十三届田际生物物理大会上，n o b e l 奖获得者e r n s t 在报告 中强调指出，n m r 用于研究蛋白质的一个主要优点在于它能极为洋细地研究蛋 白质分子的动力学，即动态的结构或结构的运动与蛋白质分子功能的关系。目目# 的n m r 技术已经能够在秒到皮秒的时间域上观察蛋白质结构的运动过程，其中 包括主链和侧链的运动，以及在各种不同的温度和压力下蛋白质的折叠和去折叠 过程。 尽管目前对蛋白质折叠的机制缺乏深刻的理解，蛋白质折叠还是有一些普遍 的特点。大量的研究表明，蛋白质折叠形成的原因主要有三个：疏水作用、二级 结构的形成和一些特殊的作用力，如二硫键等等。其中，二级结构的形成起着决 定蛋白质折叠途径的作用。肽链中近程肽段的折叠是一些二级结构形成的过程。 近程肤段的相互作用形成折叠的核心和基础，它在肽链卷曲中的作用就象结晶时 的晶核。另有研究表明口】，蛋白质折叠形成过程主要有三种机理：第一，无规则 的有机链经过一个简单的反应，折叠为天然状态。第二，蛋白质从端开始逐渐 卷曲，经过一系列连续的中问过程，最后形成折叠。第三，蛋白质折叠时，先在 链内形成一个有机结构的核心，再在此核心上折叠形成其余部分，进而形成一个 完整的折叠。 1 5 从头预测方法预测蛋白质折叠问题 在1 3 节介绍蛋白质结构预测的方法时我们提到了从头预测方法，该方法不 仅能够预测蛋白质三级结构还能够预测蛋白质折叠。下面我们将着重介绍解决蛋 白质折叠闯题的各种从头预测方法。其中，分子动力学( m d ) 方法是被深入研 究过的方法之一。用该方法来解决蛋白质构象的搜索问题可以看作是试图再现蛋 白质折叠这一真实的物理过程。在笛卡儿空间中使用全原子力场( f o r c ef i e l d ) 和外部溶剂描述的分子动力学( m d ) 方法所建立的时间函数，被认为能够可靠 再现多肽链的运动。如果上述理论成立，那么从一个随机结构出发，只要产生一 条足够长的轨道，就可以找到功能构象。但是即使是一个短肽，搜索其构象空间 的计算量也是十分巨大的。特别是随着蛋白质序列中残基数目的增加，构象空间 呈几何级数增加。一条多肽链的所有可能的构象实在是太多了，不可能用穷举法， 这就构成了n p 难题。 目前，所使用的加快模拟速度的两种方法为简化多肽链模型或者在搜索中采 取较大的步长。但是，大的搜索步长一般在二面角空间中由蒙特卡罗( m c ) 方 法产生，而不是在笛卡儿空间中。对构象中个别的或一小组扭角进行较大改变的 试验，并计算由此而改变的系统能量。如果能量值减少，则接受新构象；反之， 上海大学硕士学位论文新蒙特卡罗方法在蛋白质折叠模拟上的应用 则根据基于m e t r o p o l i s 试验的接受准则判断是否接受新构象。m d 和m c 方法都 可以看作是试图再现蛋白质折叠这一真实的物理过程。其它还有许多方法来解决 蛋白质折叠预测问题，包括确定性方法( 局部搜索方法、系统搜索方法等) 以及 各种随机算法( 模拟退火算法、遗传算法等) 。 局部搜索方法的主要思想是，从一个随机的初始解开始，在这个解的邻域中 搜索一个更好的解，然后转到这个新解，再在它的邻域中寻找更好的解。算法反 复执行，直到无法找到更优解。显然，该方法的缺点是解的好坏依赖初始解和邻 域的选择。当该方法找到一个局部最优解后，算法就终止了。局部搜索方法的改 进思想是，不仅接受更好的解，还要在一定程度接受较差的解，以便跳出局部最 优解。 系统搜索方法的主要思想是，系统地搜索整个构象空间来寻找能量最小值。 晟基本的系统搜索方法是在构象空间中逐点搜索，即变量以很小的幅度改变，如 果改变足够小的话，就有可能搜索到所有的点，来找到全局最小值。但是这样的 方法类似穷举法，计算量实在太大。系统搜索方法还有些改进的方法，在这就不 再介绍了。 确定性方法由于算法本身的问题，并不能很好地解决蛋白质折叠问题。随着 各种随机算法的兴起并应用到各个领域，人们发现这些随机算法对于解决蛋白质 折叠问题有其特有的优点。特别是随机抽样方法即蒙特卡罗方法由于它本身的优 点( 方法不受解空间结构和分布的影响) 渐渐引起了人们的兴趣。在下一章中， 我们会详细地介绍蒙特卡罗方法。 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 第二章蒙特卡罗方法 2 1 基本蒙特卡罗方法 蒙特卡罗方法( m o n t ec a r l o ，m c ) 的定名和系统发展约始于二十世纪四十 年代，它的雏形可以追随到十九世纪后半叶的蒲丰( b u f f o n ) 随机投针试验，也 就是我们所熟悉的用随机试验求兀值的范例。一般情况下，随机抽样试验的精度 是不高的，直到本世纪四十年代，由于电子计算机的出现，利用电子计算机可以 实现大量的随机抽样试验，才使得用随机试验方法解决实际问题有了可能。 蒙特卡罗方法的基本思想【6 】是：为了求解数学、物理、化学、工程技术以及 生产管理等方面的问题，首先建立一个概率模型或随机过程，使它的参数等于问 题的解；当所解的问题本身属于随机性问题时，则可以采用直接模拟法，即根据 实际物理情况的概率法则来构造蒙特卡罗模型：然后通过对模型或过程的观察或 抽样试验来计算所求参数的统计特征，最后给出所求解的近似值。该方法的优点 是：程序结构简单：收敛速度与问题维数无关，不受解空间结构和分布的影响： 适应性强。它的缺点是，没有充分利用所要解决的问题本身提供的启发式信息， 因此在实际应用时，需要较多的计算时间才能给出较好的解，收敛速度的主阶为 o ( n 1 垃) 。 从理论上说，利用蒙特卡罗方法可以得到全局最小值，但是由于受到计算机 资源的限制，传统的蒙特卡罗方法往往被限制在能量的局部极小值状态中。一般 可以从两个方向对蒙特卡罗方法进行改进。第个改进的方向为改进采样方法； 第二个改进的方向为改进构型更新方法。下面我们就这两个方向上的进展作系统 介绍。 2 2 关于采样方法的改进 1 9 5 3 年m e t r o p o l i s 等提出重要性采样方法( i m p o r t a n c es a m p l i n g ) 7 1 ，也称 为正则采样。此方法以波尔兹曼概率进行采样 _ p ( z ) 芘e x p 一声g 】，尸( 印芷n ( e ) e 一声( 2 2 1 ) 其中= l k t ，k 是波尔兹曼常数，r 是温度，( e ) 是拥有能量e 的构型数。 如果算法满足具体平衡条件，并且每一个构象都能在有限的步数中得到，即 算法是各态遍历的，那么产生的马尔可夫过程将会收敛到正则分布。但是在实际 的模拟中，往往存在某些不可达状态，而且即使是一个各态遍历的体系，由于模 拟时间无法足够长，也无法真正做到各态遍历，所以系统容易陷入局部极小值。 1 9 8 8 年，f e r r e n b e r 等提出柱状图方法( h i s t o g r a mm e t h o d ) 8 j ，它的主要思 想是，在能量e 的平衡位置附近通过改变温度r 来采样。但是此方法也存在如上 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 述重要性采样方法一样的问题。 为了克服这一问题，人们陆续提出了许多改进的方法，称为基于非玻耳兹曼 概率分布的“推广的采样”。利用这些人为的采样方法，可以得到所要物理量的 非正则分布。下面将逐个介绍这些采样方法。由于这类方法有许多，为了避免显 得凌乱，大致将这些方法分为三类，一是与熵采样方法有关的，一是不同温度下 的模拟方法，还有就是其它种种方法。 2 2 1 与熵采样方法有关的方法 第一个方法是多个柱状图方法( m u l t i h i s t o g r a mm e t h o d ) 9 1 ，此方法是在柱 状图方法上的直接改进，取k = x 。i ”= l ，r ) ，也就是取多个柱状图。详细的公式 可见 9 。第二个方法是微正则采样( m i c r o c a n o n i c a le n s e m b l e s ) 0 0 ，此方法主 要是获得相关的小系统的整个配分函数。这两种方法的主要的缺点是，需要对误 差进行较为系统和精确的分析以及需要在不同温度下进行多次模拟。 较好的方法是称为多正则采样( m u l t i c a n o n i c a le n s e m b l e s ，m c e ) i l l 的第三 种方法，或者也可以称为熵采样方法( e n t r o p i cs a m p l i n g ，e s m c ) 【2 2 】【1 3 】。可以证 明这两种方法在数学上是等价的【1 3 1 。 多正则采样( m u l t i c a n o n i c a le n s e m b l e s ，m c e ) 在采样时基于类似玻耳兹曼 的权重，但是它对于不同的能量使用不同的温度子集，以此来越过能量障碍。它 的基本思想用一句话概括就是，给所有的能量分配相同的概率。为了做到这一点， 可令 p ( ) n ( e ) e 一8 = c o n s t ( 2 2 2 ) 其中 p 一烈6 = e x p 一( + + 矿( e ) ) 一p ( ) ( 2 2 3 ) 当固定( e ) ，妒( 五) 时，该方法就退化成正则采样方法，此时原正则采样方法中的 = p + ( e ) 。根据( 2 2 2 ) 式以及( 2 2 3 ) 式，可以得到e 一( 啪一p ( 】c cp f ) 一。 但是由于j p ( ) 一开始也是不知道的，所以一般可使用迭代方法来确定 ( e kp ( 点) 。具体如何迭代，可以参考下面介绍的熵采样方法，也可以参考文献 1 1 。 熵采样方法( e n t r o p i cs a m p l i n g ，e s m c ) 的主要思想是，系统在温度无穷高 的情况下对熵采样。在无穷高温度的时候，卢：0 。此时，配分函数变成 z l a = 0 ) = e l = z e x p s ( e ) 。e ( 2 2 。4 ) 此时构象x 和能量e 的出现概率分别是p ( x ) t e - s 5 ( m 7 和尸( e ) * n ( e ) e - 研e ( 州m 。同 多正则采样方法一样，不同能量状态出现的概率是一个常数。注意，是不同能量 9 上海大学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟上的应用 状态，并不是不同构象。以，( e ) 来近似模拟s ( ) ， 因为 j d ( ) 。v ( e ) g j ( e ) k ：p 【s ( 卜j ( e ) l k ，所以当，( ) 小于s ( e ) 时，能量e 将会以较高的 概率出现；同样如果，( e ) 大于s ( e ) 时，能量e 将会以较低的概率出现。由于 s ( e ) ：k l n ( e ) ，所以通过一系列的迭代，最后，( e ) 会逐渐接近s ( e ) 。，( e ) 的迭 代方式可记为 w ，= 雠r 幅蠹薰鬻冀 。2 5 其中h ( e ) 表示在能量e 和e + 业之间的构型数。 熵采样方法的优点是它总能跳出能量陷阱，得到能量的全局最小值；而它的 缺点就是比较费时，需要较长的时间才能收敛。 2 2 2 不同温度下的模拟方法 除了上述与熵采样方法有关的方法，还有另一种方法就是实现不同温度下 的模拟。在高温下，新构型的接受概率比较大，也就更容易越过能量障碍。通 过交换不同温度下的状态，较高的温度下的构型能够帮助较低的温度下的构型 越过能量障碍，从而实现各态遍历。主要有两种方法来实现此思想。一是不同 的( 动力的) 温度下的单一的模拟，称为模拟回火方法；一是并行模拟，每一 个构型都拥有一个固定的温度，称为复制模拟或者并行回火方法。 在模拟回火方法( s i m u l a t e dt e m p e r i n g ) 【1 4 中除了传统的重要性采样外， 还引进新的转移概率 p = m i n t ，e x p ( 风+ l 一以) h + 一“】( 2 2 6 ) 其中吼称为调整参数，可以有不同的取法。 复制模拟( r e p l i c as i m u l a t i o n ) 或者并行回火方法( p a r a l l e lt e m p e r i n g ) u 6 的主要思想是交换不同温度下的构型。随机交换第i 个构型和第，个构型，而不 交换与这两个构型相联系的温度。此交换被接受的概率为 p = r a i n ( 1 ，e x p ( - a ) ) ，其中a = ( 1 k 日f ，一t k 8 r ) ( ( z 。) 一胃( 鼻，) )( 2 , 2 7 ) 重要性采样方法，熵采样方法和复制模拟方法的比较可参考 1 7 。通过对找 到最低能量状态的能力和计算花费时间的比较，可知熵采样方法和复制模拟都能 找到最低能量状态，而复制模拟花费的时间远远低于熵采样方法。但是熵采样方 法对于计算系统中其它的热力学量非常有效。 作为并行回火方法的一种改进，并行帽子回火方法( p a r a l l e l h a tt e m p e r i n g ) ”酗显然更为有效。与前述方法比较，此方法中交换被接受的概率为 p 2 a e x p ( , o , 一岛) ( ，一e ，) 】( 2 2 8 ) 共甲l 工i a = 4 2 ( i e ，一( e ， 叮一i e 。一 1 a ，+ 1 e 。一 l 寸，一? e ，一 i c r ，) ， 圭塑查堂堡圭兰垡堡奎 堑矍壁星塑堕垄至皂要堑墨坚丝二! ! 堕旦 为平均能量，。为标准方差。在 1 8 中，还介绍了另一种权重因子 w ( ) ：e x p ( - e k 日r + 压l e 一 i 0 9 ，而 和口的定义如上a 2 2 3 其它采样方法 除了上面介绍的种种采样方法，其实还有许许多多采样的方法。注意到熵采 样方法和模拟回火方法有一个共同点，那就是权重因子不是预先得到的。广义系 综蒙特卡罗方法( g e n e r a l i z e d e n s e m b l em o n t ec a r l om e t h o d ) 【1 9 】却可以直接得到 权重因子。权重为 w ( e ) = ( 1 + 兰二鱼) 1( 2 2 9 ) 月f 其中岛是能量的初始估计，n ，是系统的自由度数。只要找到能量的初始估计， 就能预先得到此权重表达式。 如前面所说，有许多权重因子不能很明确地得到，可以通过一定的方法得到 权重，从而得到每一能量的状态密度。1 l 【采样方法2 0 1 却是在每一步中不断调整 权重，从而使得能量分布逐渐收敛。取权重因子 w ，= “女 ( 2 2 。1 0 ) 其中k 。是能量达到巨的状态个数，这也就是此采样名称的由来。也可以用t s a l l i s 权重口1 1 w ( x ) = 【1 一( 1 一g ) 胚( x ) r “1 - ”，q 1( 2 2 1 1 ) 来代替玻耳兹曼权重。当q 等于1 时，方法就退化为正则采样。雨伞采样( u m b r e l l a s a m p l i n g ) 1 2 2 1 可以说是较早出现的非物理采样方法，主要是在系统的哈密尔敦函 数中增加偏倚势能，也称为雨伞势能( u m b r e l l ap o t e n t i a l s ) ，偏倚势能主要是通 过试验和误差来定义。对此方法的改进，即自适应雨伞采样( a d a p t i v e u m b r e l l a s a m p l i n g ) 2 3 】主要通过迭代的方法来获得采样。 2 3 构型更新方法的改进 在实际模拟中，传统的蒙特卡罗方法不是各态遍历的。除了上面介绍的通过 种种采样的方法来实现各态遍历，还可以通过不同的构型更新方法来保证各态遍 历。不同构型更新方法的好坏标准还在于对计算机资源的消耗程度上。 较早应用到蛋白质折叠问题上的蒙特卡罗方法是最小化蒙特卡罗方法 ( m c m ) 【2 4 】。在此方法中，构型通过大量的随机变动来更新( 主要是在1 8 0 1 8 0 范围内改变二面角的度数) 。此方法的一个有意思的改进是基于自由能的蒙特卡 罗方法( f m c m ) 2 5 o 自由能只= e 。一t s 。，s ，是熵，以此来代替m c m 中的能 量。 上述两种方法中，二面角的改变是在1 8 0 1 8 0 范围内。但是蛋白质并不是 上海大学硕士学位论文新蒙特卡罗方法在蛋白质折叠模拟上的应用 搜索所有的构型来得到它的功能构型，而只搜索在合理的时间内可以得到的合理 的构型。基于这一思想，扩散过程控制的蒙特卡罗方法 ( d i f f u s i o n p r o c e s s - c o n t r o l l e dm c ) 【2 6 在对残基进行改变时，计算二面角的改变 度数之和，只有当总和小于预先给定的某一数值时才接受这一改变。 在进行蛋白质折叠模拟时，有一个较好的简化的模型网格模型( 有关网 格模型的介绍详见论文3 1 小节) 。其基本做法是将空间离散化，即链单元只能 取空间中某些人为规定的格点。常用的网格模型有：方格子模型、金刚石模型、 石墨模型、三角点阵模型等等。针对网格模型，人们提出了一些新的构型更新的 方法。除了最简单的对某几个位点进行改变外，在 2 7 中提出了对一些特定的结 构进行整体更新的方法。但是这些方法的一个特点是要将一条链突变到原本并没 有被占据的位点上。如果链较长，那么随着模拟的进行，可以被占据的位点将越 来越少，从而导致模拟的失败。长范围移动方法( l o n gr a n g em o v e s ) 2 8 1 可以克 服这个缺点。它通过断裂、台并来产生新的构型，而不用占据新的位点。实验证 明此方法对于长链特别有效f 2 9 i 。 我们不但可以如上所述对构型进行改变，还可以将整个构型打断，重新构造 后半部分。在构型偏爱蒙特卡罗方法( c o n f i g u r a t i o n a l b i a sm o n t ec a r l o ) 1 3 0 】中， 随机选择一条序列i 和一个位点，将位点，之后的所有结构都去掉；然后使用 r o s e n b l u t h 自避免随机行走方法来重新产生后半段序列。选择位点的概率是 口 p = l r ( 2 3 1 ) 鲁_ 其中分子是随机选择的这一位点所产生的玻耳兹曼权重，分母是所有1 1 - 个可用的 位点的玻耳兹曼权重之和。根据此概率来选择下一个位点。当整条序列都被构建 好之后，相应的r o s e n b l u t h 权重因子为 月 e 既= l 一i ( 2 3 ，2 ) 与构型偏爱蒙特卡罗方法较为相似的是链增长方法( c h a i ng r o w t h m e t h o d s ) ，此方法近期的一个改进是消除一浓缩r o s e n b l u t h 方法( p r u n e d e n r i c h e d r o s e n b l u t hm e t h o d ，p e r m ) 3 1 1 。在此方法中权重为 2 * e x p ( 一皿邑) 一i( 2 3 3 ) 其中啊= 1 ，m 。表示第n 个单体有m 。个可以占据的位子。设置两个阈值吲、孵。 当权重小于吲时，此构型有一半的概率被取消，有一半的概率被保留，此时它 的权重加倍，这样就能逐渐消除那些权重很小的构型。同样，当权重大于孵时， 上海太学硕士学位论文 新蒙特卡罗方法在蛋白质折叠模拟t 的应用 复制此构型，而此时它们的权重就相应的变为原先权重的一半，通过此措施使得 样本空间中较好的构型数量越来越多。 在高温下，新的构型较容易被接受，而随着温度的降低，蛋白质折叠越来越 容易被限制在局部极小状态中。基于这一基本思想，有许多新的构型更新方法与 温度相联系。其中一个方法就是j - w a l k i n g 方法p ”。在此方法中，构型有两种可 以改变的途径。一是我们熟悉的重要性采样方法，在我们感兴趣的温度内，