（计算机软件与理论专业论文）关于蛋白质折叠构形预测问题的一个perm改进算法.pdf

华中科技大学硕士学位论文 摘要 蛋白质构形预测问题就是根据组成蛋白质的氨基酸序列来预测其空间折叠结 构。蛋白质是一类重要的生物大分子，是生命活动的主要承担者。只有当组成蛋 白质的氨基酸序列折叠成正确的三维空间结构才能使其具有正常的生物学功能。 研究蛋白质的根本目的是要将天然蛋白质进行改造，或者设计非天然的新蛋白质 以满足人类的需要。这种改造和设计的重要基础就是对蛋白质结构进行预测。 对蛋白质结构的预测最初主要使用各种实验方法。但是，由于蛋白质分离纯 化技术要求高，蛋白质晶体难以培养等原因，这些方法都受到很大制约。研究发 现，蛋白质的天然结构形式完全包含在相应分子的氨基酸序列的信息之中。这一 观点奠定了通过理论计算的方式进行蛋白质构形预测的理论基础。针对该问题的 h p 格点模型，已经提出了许多近似算法，其中最具代表性的有遗传算法、模拟退 火算法、基于重要性抽样的s i s p e r 算法以及基于裁减复制策略的p e r m 算法等。 这些算法取得了一定的进展，但其求解效率仍然有待进一步提高。 p e r m 算法是一种链生长算法。它通过制定一定的评判准则，让有前途的个 体得以繁衍，而不具备发展潜力的个体停止繁殖，从而减少了搜索的分支数。从 拟物拟人的角度对该算法进行分析，并且提出了两个拟物拟人策略：人口政策策 略和人生预测策略。通过对人类社会中人口控制政策的模拟，对影响p e r m 算法 效率的关键因素如权重、上限、下限等重新给出定义。通过对人生预测准确性的 分析得到启发，在链生长的前期降低复制的门槛，在链生长的后期提高复制的门 槛。综合这些策略，制定了更有效的评判准则，对p e r m 算法进行改进。用国际 公认的算例做检验，计算结果表明改进p e r m 算法在求解蛋白质折叠问题时表现 出非常高的效率。 关键词：蛋白质折叠，裁减复制算法，亲疏水格点模型，拟人算法，拟物算法 华中科技大学硕士学位论文 a b s t r a c t p r o t e i ns t r u c t u r e p r e d i c t i o np r o b l e m i st o p r e d i c t t h ed i m e n s i o n a l f o l d i n g c o n f i g u r a t i o n sf r o mi t s a m i n oa c i ds e q u e n c e b e i n gak i n do fi m p o r t a n tb i o l o g i c a l m a c r o m o l e e u l e s ，p r o t e i n su n d e r t a k et h em a j o r i t yo fl i f ea c t i v i t i e s o n l yw h e nt h e i r a m i n oa c i d s e q u e n c e sf o l dc o r r e c t l yi n t o c e r t a i n3 - d i m e n s i o n a lc o n f i g u r a t i o n s ，c a n p r o t e i n sf u n c t i o np r o p e r l y t h eu l t i m a t ep u r p o s eo fs t u d y i n gp r o t e i n si s t om o d i f y n a t u r a lp r o t e i n so rt o d e s i g na r t i f i c i a lp r o t e i n si no r d e rt om e e tt h er e q u i r e m e n to f h u m a n s ，t h ep r e c o n d i t i o no f w h i c hi st os o l v et h ep r o t e i ns t r u c t u r ep r e d i c t i o np r o b l e m i n i t i a l l y ，t h ep r i m a r ym e a s u r eu s e dt op r e d i c tt h es t r u c t u r e s o fp r o t e i n si s b y e x p e r i m e n t s h o w e v e r , t h i sk i n do f m e t h o d i sl a r g e l yc o n f i n e db e c a u s eo f t h ed i f f i c u l t y i n g e t t i n g t h e p r o t e i nc r y s t a l s r e s e a r c h e sh a v e s h o w nt h a t p r o t e i n sd i m e n s i o n a l s t r u c t u r ei sd e c i d e d b y t h e i ra n m i n oa c i ds e q u e n c e s ，w h i c hm a k e si tf e a s i b l et og e tt h e p r o t e i n ss t r u c t u r eb y t h e o r e t i c a lc o m p u t a t i o n m a n ya l g o r i t h m sh a v eb e e n p r o p o s e d f o r h pl a t t i c e f o l d i n gp r o b l e m ，s u c h a st h e g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n g ， s i s p e ra n dp e r m a l lt h e s em e t h o d sm a k es o m ep r o g r e s s ，b u ts t i l ln e e dt ob e i m p r o v e d p e r mi sak i n do fc h a i ng r o w t h a l g o r i t h m b yf o r m u l a t i n gs o m e c e r t a i n j u d g m e n t c r i t e r i a ，i te n r i c h e st h o s ep r o m i s i n g b r a n c h e sa n d p r u n e s t h o s eo n e sw i t h p o o rq u a l i t i e s p e r mi s a n a l y z e db yq u a s i - p h y s i c a l a n dq u a s i s o c i o l o g i c a lm e t h o d sa n dt h e nt w o s t r a t e g i e s a r ep r o v i d e d ：p o p u l a t i o nc o n t r o ls t r a t e g ya n dl i f ep r e d i c t i o ns t r a t e g y b y l e a r n i n gt h es t r a t e g i e so fp o p u l a t i o nc o n t r o l ，s o m en e w d e f i n i t i o n sa r ep r e s e n t e d ，s u c h a sw e i g h ta n dt h r e s h o l d s b ya n a l y z i n gt h er u l eo fl i f ep r e d i c t i o n ，t h ei m p r o v e dp e r m t e n dt od e c r e a s et h et h r e s h o l d si nt h ep r o p h a s eo f p o l y m e rg r o w t h ，a n d t oi n c r e a s et h e t h r e s h o l d si nt h ea n a p h a s e c o m p u t a t i o n a lr e s u l t si n d i c a t et h a tt h ei m p r o v e dp e r m p e r f o r m se f f i c i e n t l yw i t h b e n c h m a r k s o f p r o t e i nf o l d i n gp r o b l e m k e y w o r d ：p r o t e i nf o l d i n g ，p e r m ，h p l a t t i c em o d e l ，q u a s i p h y s i c a l ，q u a s i - s o c i o l o g i c a l i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到，本声明自百i 磊结果由本人承 担。 学位论文作者签名：崔饺林 日期锄归如7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阋。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密彤 ( 请在以上方框内打“”) 学位论文作者签名：崔谈弗太 日期叠谚妒7 日。 华中科技大学硕士学位论文 1 1 问题的提出 1 绪论 本课题来源于国家9 7 3 计划资助项目( 6 1 9 9 8 0 3 0 6 0 0 ) ，项目名称为“数学机 械化与自动推理平台”。本项目是一个涉及数学、信息、物理、机构学、数控机床 等多个领域的交叉前沿项目。数学机械化研究是我国学者开创的个基础研究领 域，是中国古代数学机械化思想在信息时代的复兴。数学机械化研究在国际上产 生了重要影响。本项目以数学机械化研究为核心，开展数学机械化理论与方法的 研究、力争保持我们在这一领域的特色与在几何机器证明方面的国际领先地位； 解决我国迫切需要占领的信息技术领域与其他高科技领域中一些关键基础理论问 题：以此为依据，发展智能型自动推理平台，为我国科学研究与技术创新中的脑 力劳动提供工具。 蛋白质折叠问题就是如何从组成蛋白质的氨基酸序列来预测该蛋白质的空间 折叠结构。蛋白质折叠构形预测问题是当今最有研究价值的问题之一，它不仅是 一个具有重大突破性意义的基础科学问题，而且具有重大的实际应用价值。我们 研究蛋白质的根本目的是要将天然存在的蛋白质按照人们的设想进行改造，或者 根据需要设计出具有某种特殊功能的非天然的新蛋白质，而这种改造和设计的重 要基础之一是蛋白质折叠结构的预测。 蛋白质是类重要的生物大分子，在体内占有特殊的地位，是生命活动的主 要承担者，是生命现象的主要物质基础。一切生命活动无不与蛋白质有关。我们 身体内的任何功能，从催化化学反应到抵御外来侵略都是蛋白质作用的结果；我 们能行走、运动靠的是肌肉中肌动蛋白的工作；我们身体的骨架是由蛋白质骨胶 原加强的；细胞的正常分裂或癌变也是通过蛋白质调节控制的。研究发现，蛋白 质的生物学功能分为以下几类【1 ：催化功能、运输功能、营养和存储功能、收缩 和运动功能、结构功能、防御功能、调控功能等。 华中科技大学硕士学位论文 = = t 自= 龆i ,i , i 自 自t 目目e 自自自 目，自自； = = = = 目= | = = = = = = = = = = = = = e = ：= = = = = = = = e = = = = = = = = = 自自= = = j = = j e 自j 掌 令人非常惊奇的是具有上述不同性质和功能的所有蛋白质都是由相同的2 0 种氨基酸组成的。每一个蛋白质都有它自己特有的一定的氨基酸组成和氨基酸排 列顺序，这个氨基酸的排列次序叫做蛋白质的一级结构。具有完整一级结构的蛋 白质，只有当其折叠形成正确的三维空间结构才可能具有正常的生物学功能。如果 这些生物大分子的折叠在体内发生了故障，形成错误的空间结构，不但将丧失其 生物学功能，甚至会引起疾病。研究发现，人的纹状体脊髓变性瘸( c r e u t z f e l d j a k o b d i s e a s e ，c j d ) ，老年痴呆症( a l z h e m e r ) ，亨丁顿氏舞蹈病( h u n t i n g t o n ) ，帕盒 森氏病( p a r k i n g s o n ) 和淀粉样蛋白病( s y s t e m i c a m y l o i d o s e s ) 等与蛋白质的折叠结构 异常相关。清楚蛋白质的折叠构形无论是对生物学的发展，还是对人们生活和健 康都有重大的意义。 1 2 国内外的研究现状 1 2 ，1 实验方法的研究现状及其局限 蛋白质晶体x 射线衍射技术是目前蛋白质空间结构测定的主要方法【2 1 。从 1 9 5 9 年第一个肌红蛋白晶体结构的测定开始到1 9 9 6 年底，用x 射线衍射和核磁 共振方法确定了空间结构并存入数据库的蛋白质已经接近5 0 0 0 ，其中还包括像细 胞色素氧化酶和捕光蛋白复合体那样的多亚基的大分子和大分子复合体。但用x 光衍射的方法测定一个蛋白质分子的晶体结构不仅需要首先得到高质量的晶体， 还要花相当长的时间，在技术上也受到一定的限制。在结构研究领域内，近二十 年来发展起来的二维和多维核磁共振方法，已经显示了它对蛋白质在溶液中的空 间结构和运动状态方面研究的优势，现在用核磁共振方法已经解出了约5 0 0 个蛋 白质的结构，由于不需要结晶，测定可以在溶液中进行，较之晶体x 射线衍射方 法有其在样品制备上的优越性。但这一方法目前还只限于较小的蛋白质的结构测 定。 随着分子生物学技术的飞速发展，蛋白质氨基酸序列的测定速度大大加快了。 华中科技大学硕士学位论文 蛋白质中氨基酸残基从氨基端向羧基端的排列顺序，或简称氨基酸序列通常称为 蛋白质的一级结构【2 】。1 9 5 7 年，s a n g e r 测定了含有5 1 个氨基酸残基的胰岛素分 子的氨基酸序列并阐明了其二硫键的连接方式，这是蛋白质一级结构测定的开端。 现在蛋白质氨基酸序列的测定方法，在灵敏度及自动化两方面都有了很大进展， 一个蛋白质的全序列测定所需样品在皮克( 1 0 _ 1 2 克) 范围。但是与此同时，核苷酸 序列测定技术的进展更加迅速，测定、方法的灵敏度及自动化程度更高，因为蛋 白质氨基酸序列是由核苷酸序列的三联体密码子决定a 蛋白质的氨基酸序列可以 更为方便地根据编码这一蛋白质的m r n a ，经反转录得到豹e d n a 序列而推断得 到，这已经成为当前测定蛋白质中氨基酸序列的主要方法。虽然如此，为了检查 反转录过程或d n a 测序时可能发生的错误，有时也需要用独立的测定氨基酸序 列的方法核对。最灵敏的方法，是用特定的蛋白水解酶把待测的蛋白质分解成为 多个一定长度的肽段，然后用毛细管电泳和离子电喷雾质谱仪联机对所得到的肽 段进行分离井测序。目前，有超过1 0 万种的蛋白质氨基酸序列已经被测定而进入 数据库。 自从a n f i n s e n 等人根据变性的核糖核酸酶在一定条件下可以自发地再折叠形 成天然酶分子的实验提出蛋白质分子的一级序列完全决定其三维空间结构的著名 论断以来【3 1 ，根据蛋白质的氨基酸序列，从理论上预测其相应空间结构就成为蛋 白质研究领域内科学家们的奋斗目标。除了蛋白质折叠问题本身的理论意义外， 这一问题的解决也具有极其重要的实际意义。由于蛋白质的功能与其空间结构密 切相关，对蛋白质分子空间结构的认识就成为深入了解该蛋白质如何行使其生物 功能的先决条件。如果彻底了解了蛋白质折叠的规律，我们就可以根据实际的需 要设计出新型的蛋白质分子，例如具有较高热稳定性或较高催化活性的酶分子等。 另外，酶和其它蛋白质分子空间结构的知识也是合理的药物设计的基础。目前已 知氨基酸序列的蛋白质分子大约为9 0 0 0 0 个，而己知空间结构的蛋白质仅仅为 5 0 0 0 个左右。蛋白质分子三维结构测定的速度仍远远落后于其氨基酸序列测定的 速度。随着计算理论和计算机科学的发展，人们在通过理论计算求解蛋白质折叠 华中科技大学硕士学位论文 结构的道路上进行着不断的探索。 1 2 2 理论计算方法的研究现状 国内通过理论计算来求解蛋白质折叠构形预测的研究不多。在【4 】中，分别采 用m o n t e - c a r l o 方法、单纯遗传算法和混合遗传算法对h p 格点模型进行了计算。 从计算的结果可以看出，文中介绍的算法只对较小的算例( 链长5 0 以下) 找到了 最优构形，而且计算时间并未报道。在 5 中，用并行遗传算法对蛋白质折叠够形 预测问题进行研究，但是这种方法也是只对链长为2 5 以下的h p 链有效，对于更 长的链t 该方法获得的结果并不理想。由此可见，国内对适合较长h p 链的算法 的研究成果甚微。 国外对该问题的研究要活跃的多。有些传统的方法，如分子动力学和m o n t e c a r l o 被广泛的应用来解决该问题。但是这些方法经常会陷入能量局部极小傻的陷 阱，并且对于稍长一些的链的计算要花很长的时间。许多改进的m o n t ec a r l o 算 法被提出以图找到最低能量的构形，但是大多数的工作改进不大，有- d , 部分取 得了一定的进展。早期的研究方法可以分为几类：模拟煺火算法f 6 】，m o n t ec a r l o 最小化【7 1 ，遗传算法嘲，还有进化m o n t ec a r l o 算法f 9 1 。随后人们研究较多的是链 生长算法( c h a i ng r o w t hm e t h o d s ) ，这一类的算法又演化出了c g ( c o r e d i r e c t e dc h a i n g r o w t hm e t h o d ) 算法e 1 叭，p e r m 算法 1 1 , 1 2 , 3 1 和s i s p e r s 算法1 1 4 】。下面简要介绍了 几个计算结果较好的算法。 1 9 9 9 年，g e o r g ec h i k e n j i 等人基于m o n t ec a r l o 方法的框架提出t m s o e ( m u l t i - s e l f - o v e r l a p ) 算法【l 引。该算法在计算的过程中减弱“单体不重叠”的条件， 即允许几个单体重叠在同格点的构形存在，但是根据重叠的程度给予一定“惩 罚”。在计算过程中这些不合法的构形充当了过渡到最优构形的桥梁，从而加大了 得到最优构形机率。m o s e 算法成功的找到了一个链长1 0 0 的算例的最优构形，但 是计算所花的时阎太长了( 5 0 d , 时) 。而且m o s e 对另外的一个链长1 0 0 的算例没 能找到最优构形。 华中科技大学硕士学位论文 2 0 0 2 年，由j u n n il z h a n g 和j u ns l i u a 提出t s i s p e r s ( s i sw i t h p i l o t - e x p l o r a t i o nr e s a m p l i n g ) 算法。该算法是在s i s 算法的基础上发展而来。 s i s p e r s 的一个重要改进是，当增加下个单体的时候增加一个预测策略，即对 生长方向进行一个小的抽样从而得到一些预测信息。这个预测信息在“增枝或剪 枝”时，影响着对当前构形好坏的评价。从计算结果看，s i s p e r s 的改进是有意 义的。、 在19 9 6 年p e t e rg r a s s b e r g e r 等人在r o s e n b l u t h r o s e n b l u t h ( r r ) 算法和 e n r i c h e m e n t 思想的基础上，提出了p r u n e d e n r i c h e dr o s e n b l u t hm e t h o d ( p e r m ) ”。 p e r m 也是一种链生长算法，即一条链是通过每步在其末端每次增加一个单体， 直到将所有字符放入为止。p e r m 融合了r r 算法中选择放入位置的策略，同时 将e n r i c h m e n t 的“增枝、剪枝”思想融入其中。随后有许多的算法是对p e r m 算 法的修改，其中较成功的要数h s i a o p i n g h s u 等人【1 3 1 。 13 】中指出，“增枝”时 不能只是进行简单的复制，而是要使新增构形互异。这避免了各链生长成相同的 构形，有利于保证“物种”的繁荣。实验结果证n 1 3 中的算法是一种高效算法。 1 3 课题的主要研究工作 通过对国内外研究情况的分析，我们认为p e r m 的框架对于求解蛋白质折叠 构形预测闯题表现出很强的优势。p e r m 即利用了有效的“历史信息”，又可以利 用到“预测信息”；同时，p e r m 还是一个开放式的结构，许多改进思想和策略可 以融入其中。我们希望能够分析出影响p e r m 算法效率的关键，从而为其提出更 好权重衡量策略和裁减复制策略，以此对p e r m 算法进行改进，得到求解蛋白质 折叠问题的更高效算法。 我的导师黄文奇教授是最先提出求解n p 难问题的拟物拟人算法的学者之一， 曾经先后成功的为p a c k i n g ，s a t ，c o v e r i n g 等问题找到了快速高效近似求解算 法。拟物拟人方法对于求解n p 难问题具有非常高的效率。在黄文奇教授的指导 下，对蛋白质折叠模型进行深入研究和思考，希望能用拟物拟人思想分析蛋白质 华中科技大学硕士学位论文 折叠问题和p e r m 算法，提出对p e r m 的改进策略。 基于以上的考虑，本课题拟开展以下的工作： 1 认真研究h p 格点模型，明确其中的概念，理解从真实的蛋白质结构到 h p 模型的简化过程，以期对蛋白质折叠和h p 模型有更多感性和理性的认识，为 以后的研究打下基础。 2 实践出真知，最有价值的思想来源于朴素的实践。对于较短的算例，制作 模型，动手试验，希望从中得到感悟，找到规律。总结实践过程中的经验，上升 到理论，从而制定出拟物拟人策略。 3 从拟物拟人的角度分析p e r m 算法，找出影响其效率的关键因素。将改 进策略应用到p e r m 的框架结构中，形成算法，对算例进行试算。根据计算结果 调整策略，并修改算法，克服难例，从而寻找适应性强的求解蛋白质折叠够形预 测问题的高效算法。 1 4 文章的框架结构 全文分为六章，各章内容组织如下： 第一章指出了蛋白质折叠构形预测问题的重要研究价值，并分析了国内外的 研究现状。 。 第二章详细描述了求解蛋白质折叠预测问题所用到的数学模型：h p 格点模 型。内容包括该模型建立的理论基础、该模型的精确描述、针对该模型的精确求 解算法和对该n p 完全问题求解复杂性的分析。 第三章介绍了p e r m 算法中的几个常用概念和p e r m 的核心思想。 第四章介绍了拟人拟物策略，重点描述了针对蛋白质折叠问题和p e r m 算法 所提出的几个拟物拟人策略，这是改进p e r m 算法的理论依据。 第五章实现提出的改进策略，精确描述了改进后的p e r m 算法。 第六章用国际公认的算例检验改进后的p e r m 算法，并根据计算的结果分析 该算法的优缺点。 华中科技大学硕士学位论文 2h p 格点模型 简单描述了蛋白质的组成和影响蛋白质折叠的作用力，进而详细介绍了简化 描述蛋白质折叠构形预测问题的h p 格点模型。提供了一种针对该模型的精确求 解算法，但该算法具有指数阶的时间复杂度。蛋白质折叠构形预测问题是一个n p 完全问题，是否存在多项式时间复杂度的算法? 将利用计算复杂性理论进行分析。 2 1 蛋白质的组成 蛋白质是由氨基酸( a m i n oa c i d ) 所组成的长链状巨型分子。构成蛋白质的天然 氨基酸有二十种。每一个蛋白质分子都有它自己特有的一定的氨基酸组成和氨基 酸排列顺序。虽然组成所有蛋白质的氨基酸只有2 0 种，但这2 0 种氨基酸以不同 方式排列的所有可能性却是一个巨大的天文数字。以一个仅由1 0 0 个氨基酸组成 的较小的蛋白质为例。这1 0 0 个氨基酸所有可能的排列顺序则是2 0 加o ，或1 0 b o ， 也就是说可以有1 0 1 3 0 那么多种不同的分子。即使每种分子仅有一个，其总重量也 将为1 0 0 1 0 0 吨左右，等于地球总重量的1 0 7 8 倍，太阳系总重量的1 0 7 2 倍t 2 1 。虽然 这不过是仅就一个很小的仅含1 0 0 个氨基酸的蛋白质所做的计算，但是这个数字 不但已经远远超过地球有史以来生存过的生物体的总重量，并且在生命世界继续 进化发展多少亿年以后所生成的蛋白质也不会达到这个数字。1 9 5 7 年，由胰腺分 泌的一种激素、含有5 1 个氨基酸的一种小蛋白质胰岛素分子的氨基酸序列及 二硫键连接方式的阐明，是蛋白质一级结构测定的开始。四十年来，氨基酸序列 被测定的蛋白质已接近l o 万。到1 9 9 5 年底，已经测定氨基酸序列的最大的由一 条肽链构成的蛋白质是一种肌肉蛋白：肌巨蛋e t ( t i t i n ) 。它含有约2 7 万个氨基 酸残纂，分子量高达3 0 0 万，是一个巨蛋白。 蛋白质分子除有其组成氨基酸按一定顺序以肽键相连的肽链结构以外，还具 有肽链在空间的卷曲折叠，形成特定空间排布的三维空间结构。第一个被测定空 间结构的蛋白是在肌肉中行使存储氧气功能的肌红蛋白。只有处在特定的三维结 华中科技大学硕士学位论文 构中的蛋白质分子才能够发挥其特定的生物功能。因此，即使肽链仍然完整，肽 链的氨基酸序列也不变，只要空间结构被破坏，或者说肽链在空间的位置发生了 变化，就会导致蛋白质功能发生变化乃至丧失。 天然态蛋白质的三维结构主要取决于氨基酸序列。一级结构决定高级结构。 许多实验事实证明，在给定环境( 溶剂、p h 值、离子强度、温度以及其他成分的 存在) 中，天然蛋白质处于一种相对于所有自由度来说总体系统吉布斯自由能极小 的状态，即天然态三维结构是由各种组成原子间相互作用( 也就是由组成氨基酸的 序列) 决定的。这就是蛋白质结构形成的基本原理。尽管近年来已经证实，有些蛋 白质的正确折叠需要其他因索( 如某些酶和分子伴侣) 辅助，但并未影响这一原理 核心内容的正确性。体外蛋白质复性研究是建立上述原理的主要实验基础。所谓 复性，是指变性蛋白质重新恢复到变性前的天然三维结构状态，使蛋白质丧失了 的生物活性重新恢复。美国a n f i n s e n 小组关于核糖核酸被变性试剂还原后重新折 叠的研究，加上核糖核酸酶片段互补的研究证实，酶的活性和正确三维结构取决 于它的一级结构，进而提出：在给定的环境中，蛋白质三维结构是由其组成氨基 酸序列决定的。这就是一级结构决定高级结构原理。a n f i n s e n 由此获得1 9 7 2 年的 诺贝尔奖。此外，一系列体外化学合成活性蛋白质的成功也有力地支持这一原理。 1 9 6 5 年中国科学工作者首次用化学方法合成了具有完全生物活力的结晶牛胰岛 素，表明由化学方法按天然序列连接起来的氨基酸，在合适条件下可以自动形成 正确的三维结构及其相应的生物活性。这些实验证实，决定蛋白质正确三维结构 的信息寓存于其组成氨基酸序列中。 研究稳定蛋白质天然构象的热力学基础，是了解蛋白质天然构象形成的关键。 维系和稳定蛋白质天然构象的作用力有：氢键、疏水相互作用力、范德华力、电 荷相互作用力、二硫键和配位键。疏水相互作用实质上也是一种范德华力，由于 其对蛋白质构象稳定有特殊作用，因此将其单独考虑。 这2 0 种氨基酸的物理性质和化学性质存在差异，但是对折叠结构影响最大的 、 是它们的疏水性不同。根据疏水性的不同，二十种氨基酸可以分为两类：疏水氨 基酸和亲水氨基酸 1 6 1 。疏水氨基酸和疏水氨基酸之间相互吸引，使它们与水的接 华中科技大学硕士学位论文 触面积尽量小；而亲水氨基酸对它们与水的接触面积并不敏感。正是氨基酸的这 种疏水相互作用在蛋白质的氨基酸链折叠过程中起了主要作用。 2 2 咿格点模型 根据上面的原理，人们设计出了模拟蛋白质折叠构形的h p 正交格点模型( h p l a t t i c em o d e l ) 1 7 - 2 0 1 。该模型是研究蛋白质折叠结构与折叠动力过程非常简约化 也是非常受欢迎的模型。该模型又分为二维h p 格点模型和三维h p 格点模型。 下面的讨论只是针对二维模型而言。 h p 格点模型忽略次要因素，而只考虑起重要作用的疏水相互作用。所以，该 模型只对氨基酸表现疏水性还是表现亲水性感兴趣。在这种模型中组成氨基酸链 的只有两类氨基酸：疏水氨基酸和亲水氨基酸，分别用h 和p 来表示。这样， 个氨基酸链就可以用一个p 、h 组成的字符链表示( 例如：h p h h p h p p ) ，其中的 每个字符( 或是p 或是h ) 叫做一个单体。之所以把该模型叫做二维正交格点模 型，是因为要把这个l i p 链放到一个正交格点平面上，且该平面的水平格线之间 的距离和竖直格线之间的距离都是单位长度。把h p 链放到格点平面上对要求符 合以下的条件： 条件一：每个单体必须放到格点上； 条件二：每个格点上只能放一个单体； 条件三：在h p 字符链上前后相邻的两个单体放到格点平面上后位置仍要相 邻，即他们之间的距离是1 。 按以上条件把一个h p 链放到格点平面上后，形成的布局就叫做是该链的一 个折叠构形( 如图2 1 ) 。很容易可以看出，由一个h p 链可以得到很多种不同的 折叠构形与之对应的。 一代表m 口代表p 圈2 1 能量为2 的折叠构彳亍 9 广兰譬 鞋一 华中科技大学硕士学位论文 在一个构形中。，如果两个h 在格点平面上相邻( 即他们之间的距离是1 ) 而且 在h p 字符链中的次序不前后相邻，就说它们之间形成了大小为一i 的自由能；而h p 之间、p p 之间均不会产生自由能。该构形中形成的所有自由能的和，叫作该构形 的能量( 图2 1 所示的构形的能量为一2 ) 。一个构形的能量计算公式如下： h = 毛o ( 2 ，1 ) 鼽白= ：，嚣亍符是乩聊字符射“一： k 是第i 个字符与粕个字符在格点平面上的距离。 根据自然界的规律，蛋白质折叠总是趋向于能量最低的构形。所以，算法要 做的便是对一个给定的h p 链找到能量最低的构形。 2 3 求解该问题的精确算法 长度为n 的构形可以看作长度为二的构形通过生长得到的。由此，很容易想 到的一个解决办法就是对构形的生长方向进行枚举，然后从中找到最优构形。 对于一个长为n 的h p 链，前两个单体放好以后，第三个单体有三个位置可 以放置。把第三个单体分别放置在这三个不同的位置上( 如图2 2 ) ，这样一个长 为二的中间构形就生长繁殖为三个完全不同的长为三的中间构形。用类似的方法 可以让每个长度为三的中间构形生长繁殖为所有合法的长度为四的中间构形。这 样一直生长繁殖下去就会得到所有合法的长为n 的折叠构形。然后我们再从所有 这些长度为n 的构形中找出能量最低的一个，问题不就解决了吗? 但这是对所有可能的构形的枚举，所用的时间将随链长n 的增加成指数增加。 当n 比较大时该方法根本行不通。是不是可以找到多项式时间复杂度的的精确算 法昵? 该问题是n p 完全问题【2 “，我们将从计算复杂性理论的角度来分析它的计 算复杂性。 华中科技大学硕士学位论文 力头 即一 明 头 8 3h 头- 图2 2 构形生长 2 4 该问题的计算复杂性分析 当今科学技术的发展，如果没有飞速发展、不断强大的数字计算机技术是根 本不可能的。每一个人都想了解这个神奇的创造，人们在惊叹它的强大能力的同 时，也发现它的局限。正如在计算机出现之前人们遇到的情况一样，有些问题我 们可以求解，有些问题则不可能( 在适当时间内) 求解。例如，排序是一个容易 的问题，即使是一台小型计算机也能相当快地对1 0 0 万个数进行升序排列。而时 间表问题则比排序问题困难得多。譬如说要制定所大学的课程表，课程表必须 满足某些合理的限制，如不能有两个班在同一时间使用同一教室。如果有1 0 0 0 个班，即使是使用一台超级计算机，制定一份最好的课程表也可能需要若干世纪。 也就是说，并不是所有问题的解决都可以在计算机上完成。这些不易求解的问题 可分为两种情况：一是对那些不确定的非数学型问题；二是对有些问题，虽然原 则上存在一种算法可求解其任一实例，但因该算法需要过长的时间或太大的存储 空间而使它变的完全无用。那么，到底什么问题是能计算的，什么问题是不能计 算的，计算有多快，需要多少存储空间? 能否给出一个一般的划分和度量标准， 以区分不同问题的难易程度、度量不同算法有效性之间的差异呢? 是什么使某些问题很难计算，又使另一些问题容易计算，这是计算复杂性理 论的核心问题。计算复杂性理论试图从一般角度去分析实际中各种不同类型的问 题，通过考察可能存在的求解某个问题不同算法的复杂性程度来度量该问题的难 华中科技大学硕士学位论文 易程度，由此将问题划分为不同的类型。首先，什么是算法? 所谓算法( a l g o r i t h m ) 是指可用来求解某一问题的、带有一般性的一步一步的过程。以日常用语来说， 算法又称为过程或处方。它是用来描述可在许多种计算机上实现的任一计算流程 的抽象形式，其一般性可以超越任何实现时的细节。因此，复杂性理论中对算法 的定义与我们通常所理解的具体算法用某种计算机语言编写的、可在某一特 定计算机上实现的计算机程序不同。算法在数学和计算机理论科学中起着重 要的作用。古代数学文献中包含了各种各样任务的算法描述，如寻找素数和最大 公因子。当代数学中充满了算法。称一个算法求解一个问题，是指该算法可应用 于该问题的任一个例子，并保证总能找到该例子的一个解。 广义的讲，一个算法的有效性可以用执行该算法时所需要的各种计算资源的 量来度量。最典型的、也是最主要的两个资源就是所需的运行时间和存储空间。 不过，人们通常总是将最快的算法和最有效的算法等同起来，这是因为时间需求 常常是决定某一特定算法在实际中是否真正有用和有效的决定性因素。因此，在 复杂性研究中，衡量一个算法的效果，最广泛采用的标准是在产生最终答寨前它 所花费的时间。并常常称之为时间复杂性。现今，在计算机科学中存在着这样一 个一般的约定：仅当算法的时间复杂性函数随着问题例子的输入长度的增加而多 项式的增加时，才认为这个算法是实用的、有效的。 迄今为止，复杂性理论的一个重要成果是，发现了个按照计算难度给问题分 类的完美体系。简单地说，其中的p 是成员资格可以在多项式时间内判定的语言 类，n p 则是成员资格可以在多项式时间内验证的语言类。p 类语言用来描述那些 存在有效算法的问题，即那些在确定性图灵机上可在多项式时间内解决的问题。 n p 类语言描述那些在非确定性图灵机上可在多项式时间内解决的问题。对于n p 类语言描述的问题，一定存在一个多项式p 使得该问题可以用一个时间复杂性为 o ( 2 9 ( n ) 的确定性算法来求解。 随之而来，p = n p 是否成立的问题成为理论计算机科学和当代数学中最大的 华中科技大学硕士学位论文 悬而未决的问题之一。如果这两个类相等，那么所有多项式可验证的问题都将是 多项式可判定的。大多数研究人员相信这两个类是不相等的，因为人们已经投入 了大量的精力为n p 中的某些问题寻找多项式时间算法，都没有获得成功。研究 人员还试图证明这两个类是不相等的，但是这要求证明不存在快速算法来代替蛮 力搜索。目前科学研究还无法做到这一步。 在p 与n p 问题上的一个重大进展是在7 0 年代初由斯蒂芬库克和列奥尼德列 文完成的。他们发现n p 中的某些问题的复杂性与整个类的复杂性相关联。这些 问题中任何一个如果存在多项式时间算法，那么所有n p 问题都是多项式时间可 解的。这些问题称为n p 完全的。n p 完全问题的提出有着重要的意义，在理论方 面，试图证明p 不等于n p 的研究人员可以把注意力集中到一个n p 完全问题上。 如果n p 完全问题中的某个问题需要多项式时间，那么所有n p 完全问题也一定 如此；在实践方面，n p 完全性现象可以防止为某一具体问题浪费时间，寻找本不 存在的多项式时间算法。虽然没有足够的数学知识来证明该问题在多项式时间内 不可解，但是我们相信p 不等于n p ，所以证明一个问题是n p 完全的，就成为它 的非多项式性的一个强有力的证据。 对我们来说，运行时间是多项式可以认为是小的，而是指数则认为是大的。 注意到典型的多项式，如1 1 3 ，与典型的指数2 “，在增长率上存在巨大的差异。例 如，令r l 是1 0 0 0 ，这是一个算法输入的合理规模。这种情况下，n 3 是1 0 亿，虽 然是大数，但还可以处理。然而，2 1 0 0 0 则是一个比宇宙中的原子数还大的多的数。 多项式时间算法就很多目的而言是足够快了，而指数算法则很少使用。典型的指 数时间算法来源于通过搜索解空间来求解问题，可称作蛮力搜索。例如，分解一 个数为素因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所 以这种搜索需要指数时间。对于n p 完全问题，到目前为止没有找到多项式时间 的算法。而且人们大多数认为不存在多项式时间的算法。这正是求解n p 完全问 题的困难所在! 华中科技大学硕士学位论文 管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路设计、 代码设计、图像处理和电子工程等科技领域中存在着大量的这类n p 完全问题， 比如货郎担问题、图着色问题、设备布局问题以及布线问题等，它们至今都没有 找到有效的多项式时间算法。 本文所要讨论的蛋白质折叠构形预测问题就是一个典型的n p 完全问题。由 于该问题本身所固有的计算复杂性，求其精确解的计算量往往随问题的规模呈指 数型增长，以致使用任何高速计算机都需耗费大量的时间，甚至根本无法实现。 因此，对其寻找高效可行的近似算法有着重要的实际意义和理论价值。 2 5 小结 蛋白质是由氨基酸组成的长链状巨型分子。构成蛋白质的氨基酸链除了具有 特定的次序外，还必须形成正确的三维空间结构。研究发现，天然蛋白质的三维 结构主要取决于氨基酸序列，并且天然蛋白质总是处于系统能量最小妁状态。在 维系和稳定蛋白质天然构形的作用力中，疏水相互作用起着重要的作用。 根据以上原理，人们设计了用来简化描述蛋白质折叠问题的h p 格点模型。 该模型只考虑疏水相互作用。 针对h p 格点模型，本章设计了一种精确算法枚举算法。该算法的计算 时间随问题规模的增大成指数增加，所以从实际应用的角度看是没有用处的。该 问题是n p 完全问题。根据计算复杂性理论的研究可知：对n p 完全问题一定存 在指数时间复杂度的算法，但从未找到过多项式时间复杂度的算法。而且，大多 数的研究人员认为求解这类问题的多项式时间复杂度的算法根本就不存在。因此， 寻找在合理时间内能够得到高精确度近似解的近似算法就显得异常重要。 华中科技大学硕士学位论文 3p e r m 算法的思想 p e r m 算法即p r u n e d - - e n r i c h e dr o s e n b l u t hm e t h o d ，就是要在一个长为1 1 1 的中间构形生长繁殖为长为1 1 的中间构形的过程中进行“人口控制”，在时间与精 度之间达到最好的权衡。为便于理解，首先解释了p e r m 要用到的概念并介绍了 它的发展历史，然后详细描述p e r m 算法的思想。 3 1 有关术语 本节对p e r m 算法中用到的几个基本概念作以下解释： 定义1 中间构形把一个长为n 的h p 链中的所有单体都合乎规范的放置到 格点平面上，形成的布局叫该h p 链的一个构形。因为p e r m 是一种生长型的算 法，即构成该链的所有单体是按照它们在h p 链上的次序逐个合乎规范的放入格 点平面的，这样当放入了前n ( 1 茎匹n ) 个单体时，形成的这n 个单体的布局就 日q 作该h p 链的个长为r i 的中间构形。长为n 的中间构形也就是给定的h p 链 生长到最长时形成的构形，也可以叫做最终构形。对于一个长为n ( 1 血 o ，则执行以下的步骤： 第一步：在一个长为n 一1 的中间构形生长繁殖以前，计算出该构形生长繁殖 下去是好是坏的预测值畔”。 第二步：针对该长度为n l 的中间构形“制定”出上下界：，矿。用阡? 刚 与，进行比较，来决定如何生长繁殖，具体如下： 如果暇r 4 l 2 ，则让该构形生长为长为n 的中间构形，而且 只能生成一个。 如果w 纾：，则从第n 个单体可以放置的几个位置中按照一定的优 先次序选出而且只选出一个位置，将第n 个单体放置在此，该中间构形生长为一 华中科技大学硕士学位论文 个长度为1 1 的中间构形。 如果咿n 则懒刊n 卜等肛后按照一定的优先次序从 。个位置中选出k 个互不相同的位置，让该中间构形生长繁殖为k 个互不相同 的长为n 的中间构形。 这就是p e r m 算法的核心思想。 早在1 9 9 6 年，p e t e r g r a s s b e r g e r 就提出了p e r m 算法 j 1 j 。1 9 9 7 年，h e l g e f r a n e n k r o n 与p e