（计算机软件与理论专业论文）基于遗传算法的蛋白质二级结构预测研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着后基因时代的到来，蛋白质组学研究正成为生命科学中一个重要的 研究领域。在目前的蛋白质组学研究中，蛋白质二级结构预测仍然是一项长 期的历史任务和挑战。这一领域的任何新突破，都将有助于更好地理解蛋白 质功能、人类健康和疾病的细胞组成结构，对医药、农业和生物科技等应用 领域也有着及其重要的指导意义。 本文应用生物信息学中有关蛋白质结构及其预测的理论，结合数据挖掘 的方法技术，对蛋白质二级结构预测的相关问题进行了深入细致研究。分析 研究工作主要包括以下两个方面。第一，从分析研究当前生物信息学中蛋白 质二级结构预测领域的理论知识及研究发展现状入手，找出现阶段进行蛋白 质二级结构预测所面临的困难，确定本文的研究方向。第二，按照氨基酸的 亲一疏水性质，结合从目前蛋白质数据库提取出的极具代表性已知数据，建立 起有效的数学模型：通过对关联规则、遗传算法、模拟退火等数据挖掘方法 技术的研究与分析比较，利用简单遗传算法结合关联规则的数据挖掘技术， 来实现基于简单遗传算法的模式规则挖掘，并在此基础之上完成蛋白质二级 结构的预测。同时，本文将模拟退火遗传算法引入到蛋白质二级结构预测的 模式规则挖掘中来，以克服简单遗传算法存在最为严重的“过早收敛”问题 和模拟退火收敛速度慢和易陷入局部收敛的缺陷。 最后，设计实验对在蛋白质二级结构预测中，采用的基于简单遗传算法 的模式规则挖掘策略和基于模拟退火遗传算法的模式规则挖掘策略进行分析 比较，验证算法改进的有效性和正确性。 关键词：蛋白质二级结构预测；关联规则；遗传算法；模拟退火 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h ea p p r o a c ho fp o s t - g e n o m ee r a ，p r o t e o m i c si sb e c o m i n ga l li m p o r t a n t r e s e a r c hd o m a i ni nt h el i f es c i e n c e p r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o n ( p s s p ) ， w i t hal o n gh i s t o r i ct a s k ，i ss t i l lac h a l l e n g ei nt h er e s e a r c ho fp r o t e o m i c sa t p r e s e n t a n yn e wb r e a k t h r o u g hi nt h i sa r e aw i l lb eh e l p f u lt ok n o w i n g b e r e rt h e f u n c t i o no fp r o t e i na n dt h eh u m a nh e a l t h yo rp a r o x y s mc e l lc o n s t i t u t e s w h a ti s m o r e ，i tw i l lb ea ni m p o r t a n ta s s i s t a n tt os o m er e l e v a n ti n d u s t r i e ss u c ha sm e d i c a l e n g i n e e r i n g ，a g r i c u l t u r e ，a g b i o t e c h ，e t c s o m ew o r k so nt h es t u d yo fp s s pu s i n gt h em e t h o d so fd a t am i n i n ga n dt h e t h e o r yo fb i o i n f o r m a t i c sa r ed o n ei nt h i st h e s i s f i r s t l y ，s t a r t i n gw i t ht h ea n a l y s i s o fc u r r e n tb i o i n f o r m a t i c si nt h ef i e l do fp s s pa n dd e v e l o p m e n ts t a t u s ，w et r yt o f i n do u tt h ed i f f i c u l t i e sf a c e da r i dd e t e r m i n et h ed i r e c t i o no ft h i ss t u d y s e c o n d l y ， a c c o r d i n g t ot h eh y d r o p h o b i cn a t u r eo fp r o - a m i n oa c i d s ，w eu s et h ev e r y r e p r e s e n t a t i v ed a t af r o mt h e c u r r e n tp r o t e i nd a t a b a s e sk n o w n ，t oc r e a t ea n e f f e c t i v em o d e l b yr e s e a r c h i n ga n da n a l y s i s i n gd a t am i n i n gt e c h n i q u e s ，s u c ha s a s s o c i a t i o nr u l e s ( a r ) ，g e n e t i ca l g o r i t h m s ( g a ) a n ds i m u l a t e da n n e a l i n g ( s a ) ， e t c w eu s es i m p l eg e n e t i ca l g o r i t h m ( s g a ) w i t ha rt oa c h i e v et h em o d e lr u l e s m i m n ga n dp s s p a tt h es a m et i m e ，u s i n gt h e s i m u l a t e da n n e a l i n gg e n e t i c a l g o r i t h m ( s a g a ) i n t ot h ep s s pm o d e lr u l e sm i n i n g ，c a no v e r c o m et h i ss g a m o s ts e r i o u s ”p r e m a t u r ec o n v e r g e n c e ”，a n ds o l v es as l o wc o n v e r g e n c ea n de a s y i n t ol o c a lc o n v e r g e n c e f i n a l l y ，w ed e s i g ne x p e r i m e n t st oc o m p a r es g am o d e lr u l e sm i n i n gw i t h s a g am o d e lr u l e sm i n i n gi n p s s p ，v e r i f y i n ga l g o r i t h mt oi m p r o v et h e e f f e c t i v e n e s sa n da c c u r a c y k e y w o r d s ：p r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o n ；a s s o c i a t i o nr u l e s ；g e n e t i c a 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 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：皇堕! 叁 日期：d o 口g 年j 月，o 日 哈尔滨工程大学硕士学位论文 第1 章绪论 人类基因组计划的顺利实施，使生物分子数据的数量得到了极大增长。 这些生物分子数据背后隐藏着人类目前尚不知晓的生物学知识。如何充分利 用这些数据，通过对数据进行分析、处理，进一步揭示这些数据的内涵，得 到对人类有用的信息，成为了摆在千百万生物学家、数学家和计算机科学家 面前十分严峻的挑战。生物信息学作为迎接这种挑战而发展起来的- 1 7 新型 学科，也将是2 1 世纪自然科学的核心领域之一。因此，蛋白质结构与功能预 测也将在生物信息学中占据十分重要的地位。 1 1 课题的研究背景及意义 1 1 。1 课题的研究背景 1 9 5 6 年，在美国田纳西州盖特林堡首次举行的“生物学中的信息理论研 讨会 上，产生了“生物信息学 这一概念。但就生物信息学的发展而言， 它还是一门非常年轻的学科。1 9 8 7 年，林华安博士正式命名“生物信息学 ( b i o i n f o r m a t i c s ) 。其后，生物信息学的内涵随着研究的深入和现实需要而 几经更迭。1 9 9 5 年，在美国人类基因组计划的第一个五年总结报告当中，给 出了一个较为完整的生物信息学定义：生物信息学是- 1 7 交叉科学，它包含 了生物信息的获取、加工、存储、分配、分析、解释等在内的所有方面，它 综合运用数学、计算机科学和生物学的各种工具，来阐明和理解大量数据所 包含的生物学意义n 。 生物信息学把d n a 序列、氨基酸序列、以及其它相关数据信息作为研究 和分析对象，为了揭示蛋白质和r n a 基因的编码区、基因组中非编码区信息 的实质，生物信息学还充分利用了基因组中编码区的信息来进行蛋白质空间 结构的模拟以及蛋白质功能的预测。 哈尔滨工程大学硕士学位论文 蛋白质空间结构预测是一个重要的问题，它成为近年来全世界生物学家 关注的焦点”，。d n a 序列分析技术和基因识别方法的进步，使我们可以从 d n a 推导出大量的蛋白质序列。目前测定蛋白质立体结构的实验方法主要有 两种：多维核磁共振( n u c l e a rm a g n e t i cr e s o n a n c es p e c t r o s c o p y ，n m r ) 方 法和x r a y 晶体衍射( x r a ye r y s t a l l o g r a p h y ) 方法。这两种方法都有局限性： ( 1 ) n m r 方法的主要缺点是精度较差，且对蛋白质的体积的大小有所要求 ( 只能测定较小的蛋白质) ；( 2 ) 而x r a y 晶体衍射方法对蛋白质晶体制备 要求苛刻，有些蛋白质很难获得晶体结构。 显然，通过实验方法确定蛋白质结构的过程仍然非常复杂，且代价较高。 这就意味着已知序列的蛋白质数量和已测定结构的蛋白质数量的差距将会越 来越大。因此，将基于经验和知识的方法与计算化学、统计物理学、信息学 的方法结合起来，从理论上发展预测蛋白质结构的新方法成为解决这一问题 的有效途径协”。 通过对已知空间结构的蛋白质分子的仔细研究和分析后人们发现，尽管 一条多肽链可能采取的构象数目是相当大的，但是在蛋白质分子中由二级结 构组装而形成一定的空间结构的方式却是有限的。蛋白质三级和四级结构的 预测都要建立在二级结构预测的基础之上，因此，蛋白质二级结构预测不仅 成为了联系蛋白质一级结构和三级结构的纽带，也成为了研究蛋白质结构及 其功能的一个关键问题。 现在一般认为，如果二级结构的预测准确率可以达到8 0 的话，就可以 基本准确地预测一个蛋白质分子的三维空间结构。因此，蛋白质的二级结构 不仅是联系其一级结构和三维空间结构的桥梁和纽带，而且蛋白质的二级结 构预测也是解决从蛋白质的一级结构预测其空间结构这一问题的最关键步骤 o 1 1 2 课题的研究意义 随着生物科学技术的不断发展，生物学的研究重心已经从揭示生命的所 有遗传信息转移到整体水平上的生物功能研究。蛋白质是生物功能的体现者， 2 哈尔滨工程大学硕士学位论文 蛋白质分子在生物体内执行着相当重要的任务，例如：生化反应的催化、营 养的输运、信号的识别与传递等等。生物信息学的一个基本观点是：分子结 构决定分子的性质和了功能。因此，蛋白质的结构预测，对于理解蛋白质结 构与功能的关系，进行蛋白质结构的药物设计以及突变体等设计具有重要的 意义”。 目前人们掌握的蛋白质序列数据中，只有很少一部分的蛋白质空间结构 为人们所熟识。如果能找到合适、准确和高效的算法，利用氨基酸序列来预 测蛋白质的空间结构，将会有助于丰富人们对蛋白质的认识、提高人工合成 蛋白质的效率。大量的实验结果证明：蛋白质的结构是由蛋白质序列决定的 ”，直接通过序列预测蛋白质结构对研究蛋白质结构与功能的关系十分有用， 这也将促进蛋白质工程和蛋白质设计的发展“。 1 2 蛋白质二级结构的研究发展现状 1 2 1 蛋白质二级结构预测的发展过程 自2 0 世纪6 0 年代中期至今，在大批生物信息科学工作者的共同努力下， 蛋白质二级结构预测的方法也源源不断地涌现出来，其发展过程可概括为以 下三个阶段：第一阶段是以分析蛋白质单残基、单一序列为重点，以 c h o u f a s m a n 方法和g - o r ( g a m i e r - o s g u t h o r b e r o b s o n ) 方法“引等为代表。 但是预测准确率普遍较低，大约在5 0 * , 5 9 0 , 之间。第二个阶段则考虑到了局 部残基之间的相互影响，主要的方法有1 9 8 6 年的l e v i n e t a l 方法“”，1 9 8 7 年的 g o r i i i 方法“”，1 9 8 8 年的q i a n - s e j n o w s k i 方法“”，1 9 8 9 年的h o n e y k a r p l u s 方法 “，以及1 9 9 3 年的y i l a n d e r 方法n ”。这一阶段方法的预测准确率有了一定的 提高，尤其在使用了神经网络方法后，预测准确率首次提高到了7 0 以上。 第三阶段在已有方法如g o r 方法或者神经网络方法的基础上，进一步提出了 结合多重序列比对( m u l r i p l es e q u e n c ea l i g n m e n t ，m s a ) 的思想，使预测准 确率又有所提高。使用的传统序列分析软件有f a s t a ，b l a s t 近些年又出现 了另外一些优秀软件，如p s i ，b l a s t ，h m m s 等。这一阶段的主要方法有p h d 3 哈尔滨工程大学硕士学位论文 方法m 1 ，j n e t 方法m ，以及p s i p r e d 方法1 2 0 ，等。它们的预测精度较以往方法有明 显提高，准确率在7 2 7 9 之间。 1 2 2 国内外研究发展现状 由于蛋白质工程的迫切需要和相应计算机科学技术的发展，围绕如何提 高蛋白质二级结构预测精度这一课题，捅现出了很多方法和蛋白质结构的预 测软件。国内对于蛋白质结构和功能预测与分析的研究起步虽晚，但也取得 了很大进展。天津大学的张春霆院士提出了蛋白质结构分类新的客观标准， 提高了蛋白质结构的预测精度”。中国科学院上海生命科学研究院生物信息 中心在2 0 0 2 年研究开发的跨膜蛋白二级结构综合预测( m e m b r a n ep r o t e i n p r e d i c t i o na g e n t ，m p p a ) 软件和中山大学化学与化学工程学院通过将氨基酸 序列映射为疏水值序列再利用连续小波变换方法对非规则二级结构进行预测 的研究l 篮，。 国外有在蛋白质序列分析与结构预测中，clg i l e s 等人提出了神经元网 络方法啪4 “，t h o m a see 等人使用模糊逻辑方法，n o t r e d a m ec 等人使用遗 传算法。英国d a v i dtj o n e s 实验室开发的基于神经网络算法的蛋白质二级结 构预测软件p s i p r e d ，它可以在分析p s i b l a s t 计算结果基础上进行结构 预测；以及日本三井集团和东京农业科技大学开发的基于氨基酸序列的疏 水性和所带电荷等物理化学性质预测膜蛋白的二级结构软件等啪2 ”。2 0 0 4 年 y a n ng u e r m e u r a 汹等提出采用多个支持向量机结合( m s v m ) 方法预测蛋白 质二级结构，预测精度达到7 6 7 3 。 1 2 3 面i 临的困难与挑战 根据当前蛋白质结构库中的蛋白质相似性或同源性来预测蛋白质结构， 更多地依赖于蛋白质结构库中数据的多少，这也是目前进行蛋白质结构预测 的一个难点问题胁。从代数上讲，就是蛋白质库中是否包含蛋白质结构空间 的所有基向量，一个新蛋白质和这些基向量之间又怎样的确定关系系数，以 及怎么由基向量来确定蛋白质结构。从概率上讲，则是蛋白质库中数据的样 4 哈尔滨工程大学硕士学位论文 本量是否已足够大，能否提供对未知序列预测的数据支持。足够多的样本最 后就使预测变成了模式识别。目前有些预测方法之所以准确性不高，也正是 因为统计蛋白质二级结构构象趋势的蛋白质空间结构数据量还不够多。再加 上蛋白质结构测定速度的制约，造成了蛋白质数据库容量不足的问题还将长 期存在。 1 9 6 0 年至1 1 9 9 0 年，蛋白质二级结构的预测只有6 0 左右。1 9 9 3 年r o s t 和 s a n d e r 实现的重大突破，使蛋白质二级结构预测准确率首次达到7 0 以上“。 他们之所以能够在预测准确率上有所突破，一方面是因为结合了大量的数据 和更好的算法，另一方面则主要是因为他们在预测方法中，加入了有关生物 进化的信息。 如何从海量数据中提取出更多的信息，往往对提高算法的预测准确度有 极大帮助。影响预测准确率的因素有多种： ( 1 ) 由于人类对蛋白质构象形成的机制尚未完全认识，以至于不能建立 最适宜的预测模型： ( 2 ) 与未知结构的数据相比，已知结构的数据太少，这也更进一步制约 了从已知结构数据中挖掘知识的潜力： ( 3 ) 模型结构选择的适当与否，也会影响模型性能能否达到最佳。 针对以上存在的一些蛋白质二级结构预测难点问题，本文将尝试从数据 挖掘技术入手，更深入地研究结合遗传算法等的数据挖掘技术来进一步改善 蛋白质二级结构预测，充分利用已知数据提取更加有效的信息。 1 3 本文的组织结构 本文对基于遗传算法的蛋白质二级结构预测进行了深入的研究。在对生 物信息学、尤其是蛋白质二级结构预测，以及数据挖掘的相关技术进行全面 研究和细致分析的基础上，对基于遗传算法的蛋白质二级结构预测进行了深 入的研究。 全文共分为5 章： 第1 章对要研究课题的领域进行了阐述，并对国内外的研究现状进行了 阐述，同时提出了本文要研究的方向。 5 哈尔滨工程大学硕士学位论文 第2 章介绍了蛋白质的组成与结构、蛋白质结构研究中主要用到的蛋白 质数据库、以及一些常用的蛋白质二级结构预测的方法。为进一步展开基于 遗传算法等数据挖掘技术的蛋白质二级结构预测研究做好生物信息学方面知 识的铺垫。 第3 章分析研究了数据挖掘的相关概念与技术，尤其对关联规则算法的 典型算法、遗传算法、模拟退火算法等进行了分析；同时也着重研究了关联 规则结合遗传算法的数据挖掘策略。 第4 章进行了蛋白质二级结构预测的深入研究，着重阐述了基于简单遗 传算法的模式挖掘的设计，并且结合模拟退火算法对基于遗传算法的模式挖 掘进行了改进。 第5 章设计实验，对基于简单遗传算法的模式规则挖掘和基于模拟退火 遗传算法给出了详细的数据分析和对比。从而说明了模式挖掘算法对进行蛋 白质二级结构预测的重要性。 最后是全文的总结，对本文的研究工作进行了总体的概括，并对本文研 究工作的不足以及未来的研究工作进行了展望。 6 哈尔滨工程大学硕士学位论文 第2 章蛋白质与蛋白质二级结构预测 蛋白质广泛存在于各种生物组织细胞内，是生物细胞最重要的组成物质。 随着人类对客观世界认识的不断加深和生物信息学的蓬勃发展，对蛋白质结 构和功能的研究逐渐变得极其重要和极具研究价值。蛋白质的生物功能是由 蛋白质的空间结构决定的，因而进行蛋白质结构预测对于理解蛋白质结构与 功能的关系，以及分子设计、生物制药等领域有很重要的现实意义。蛋白质 二级结构预测是蛋白质结构预测的重要组成部分，是蛋白质结构预测最关键 的步骤。 2 1 蛋白质 2 1 1 蛋白质分子的组成 蛋白质( p r o t e i n ) 一词源自希腊字p r o t e i n s ，原意是指“第一流的、第一 位的 ，科学家之所以从希腊文中选择了这个名字，就是特别强调它的重要 性。蛋白质广泛存在于各种生物组织细胞内，是生物细胞最重要的组成物质。 在生命体的许多部分中，蛋白质都是不可或缺的重要组成部分，约占人体固 体成分的4 5 。它的分布很广，诸如皮肤、头发、眼睛、指甲、骨骼、肌肉 等，几乎所有的器官组织都含有蛋白质。 蛋白质是一种具有生命活性的高分子化合物，通常由一条或多条异质高 分子链组织而成。蛋白质的基本组成单位是氨基酸( a m i n oa c i d ) ，自然界 中组成氨基酸共有2 0 种，它们均为l 型a 碳原子。中间的碳原子为旺一碳原 子，每种组成蛋白质的氨基酸的洳碳原子均连接一个氨基、一个羧基、一个 氢原子和一个侧链基团r ，见图2 1 0 不同的氨基酸是根据r 基团的不同而加以区别的。根据这2 0 种氨基酸 ( 如表2 1 ) 的极性和带电荷的性质，可以把它们粗略地分为两类：( 1 ) 极 哈尔滨工程大学硕士学位论文 l i lc o o h i - i i ；州一l hi 一炯粉 。一一一- - 。1 一- - _ _ _ 。 r + 一侧链 图2 1 氨基酸结构 性氨基酸。那些侧链含有带电荷的基团或者具有显著的电偶极矩，易于与极 性溶剂分子一水分子相互作用的氨基酸，称为极性氨基酸，或亲水氨基酸： ( 2 ) 非极性氨基酸。另一些侧链呈中性或相对无极性的氨基酸，它们称为疏 水性氨基酸。 表2 1 氨基酸标准符号表 符号意义符号意义 a ( a l a ) 丙胺酸l ( l e u ) 亮氨酸 r ( a r g ) 精氨酸 k ( l y s ) 赖氨酸 n ( a s h ) 天冬酰胺m ( m e t )甲硫氨酸 d ( a s p ) 天冬氨酸f ( p h e )苯丙氨酸 c ( c y s ) 半胱氨酸 p ( p r o ) 脯氨酸 e ( g l u ) 谷氨酸s ( s e r )丝氨酸 q ( g i n ) 谷氨酰胺 t ( 1 1 1 r ) 苏氨酸 g g i y ) 甘氨酸 w ( t r p ) 色氨酸 h ( h i s ) 组氨酸 y ( t y r ) 酪氨酸 i ( 1 i e ) 异亮氨酸 v ( v a l ) 缬氨酸 极性氨基酸：苏氨酸( t ) 、丝氨酸( s ) 、天冬酰胺( n ) 、谷氨酰胺 ( q ) 、天冬氨酸( d ) 、谷氨酸( e ) 、组氨酸( h ) 、精氨酸( r ) 、赖氨 酸( k ) 、脯氨酸( p ) 。 非极性氨基酸：半胱氨酸( c ) 、甲硫氨酸( m ) 、苯丙氨酸( f ) 、异 亮氨酸( i ) 、亮氨酸( l ) 、缬氨酸( v ) 、色氨酸( w ) 、酪氨酸( y ) 、 丙氨酸( a ) 、甘氨酸( g ) 。 8 坠玺薹三垄查兰堡圭茎警耋圣 21 2 蛋白质分于的结构分类 为了表示蛋白质的不同组织层次，经常使用一级结构和空间结构( 二 = 、四级结构) 等术语对其分子结构进行阐述，如图2 2 所示。 图2 2 蛋白质结构分类示意图 1 蛋白质一级结构 一个氨基酸的- 羧基和另一个氨基酸的n - 氨基可以通过缩水作用而连接 起来，形成酰氨键，通常称为肽键，见图示2 3 。大量的氨基酸之问可以通过 肽键首尾相连，形成一个多肽链。在多肽链中，一个氨基酸单位称为残基。 一般说来，蛋白质分子就是由一个或多个这样的多肽链组合而成的。 州丰目每o h + h i 蝌- n c 0 0 。芝“：“弋一目t ：l f 一 “ hohr 2 肚键 图2 3 肚键的形成 蛋白质一级结构( p r i m a r ys t r u c t u r e ) 就是蛋白质多肽链中氨基酸残基的 排列顺序( s e q u e n c e ) ，这也是蛋白质最基本的结构。需要指出，蛋白质一 级结构是不涉及空间概念的结构。 9 hc v p 、。ll-_1 一o |i+0 d 个r ，h 卜h 哈尔滨工程大学硕士学位论文 2 蛋白质二级结构 蛋白质二级结构( s e c o n d a r ys t r u c t u r e ) 是指借助主链( 不包括侧链) 原 子的氢键形成的具有周期性的局部空间构象。蛋白质二级结构是蛋白质复杂 的空间构象的基础。最早的二级结构定义是1 9 5 1 年由p a u l i n g 等人提出的a 螺旋和b 折叠，以及转角。1 9 8 3 年，k a b s c h 和s a n d e r 给出了更精确的描述。 ( 1 ) a 螺旋 p a u l i n g 等人对q 角蛋白( a - k e r a t i n ) 进行了x 线的衍射分析，从衍射图 中看到有0 5 - 0 5 5 r i m 的重复单位，并由此推测出蛋白质分子中有重复性结构， 并认为这种重复性结构为q 螺旋( c t h e l i x ) ，见图2 4 。a 螺旋是蛋白质中最 常见的二级结构。 ? 门争；簟、掌 ，“匆 b ；、o 叠 图2 4 蛋白质分子的螺旋 由图2 4 可以发现q 螺旋的结构特点：多个肽键平面通过廿碳原于旋 转，相互之间紧密盘曲成稳固的右手螺旋；主链呈螺旋上升，每3 6 个氨 基酸残基上升一圈，相当于05 4 r i m ； 每个肽链中一n h 的氢与它后面第四个 肽键c o 的氧之间形成氢键，氢键取向基本与中心轴平行。 i o 哈尔滨工程大学硕士学位论文 i l l ( 2 ) 1 3 折叠 a s t b u r y 等人曾对1 3 角蛋白( b k e r a t i n ) 进行x 线衍射分析，发现它具有 0 7 1 1 1 1 1 的重复单位。若将毛发a 角蛋白在湿热的条件下进行拉伸，则可拉长 到原长的两倍。由此可见，这种a 螺旋的x 线衍射图可以改变为与b 角蛋白 类似的衍射图。说明p 角蛋白中的结构和a 螺旋拉长伸展后结构相同。两段 以上的这种折叠成锯齿状的肽链，通过氢键相连而平行成片层状的结构称为 1 1 片层( b p l e a t e ds h e e t ) 结构或称p 折叠( 争s h e e t ) 。p 折叠是除1 1 螺旋之 外最常见的蛋白质二级结构。如图2 5 ，( a ) 为平行1 3 折叠片，( b ) 为反平 行b 折叠片。 r ， 籼，r 护气妒羹 一 _ i ：黛 ，、一：严一 州 一c 图2 5 蛋白质分子的p 折叠结构 b 折叠的结构特点：是肽链相当伸展的结构，肽链平面之间折叠成锯 齿状，相邻肽键平面间呈1 1 0 0 角。氨基酸残基的r 侧链伸出在锯齿的上方或 下方：p 折叠片是被不同多肽片段中- n h 和c o 基形成的链间氢键所稳定 的：两段肽链可以是同向平行的，也可以是反向平行的。即前者两条链从 “n 端 到“c 端 是同方向的，后者是反方向的。同向平行的p 片层结 构中，两个残基的间距为0 6 5 m ；反向平行的b 片层结构，则间距为o 7 m 。 ( 3 ) 1 3 转角 b 转角( b t u r n ) 是球状蛋白质的重要二级结构，它在其他二级结构之间 1 1 乏， m i nc o 心 s u p p o r t c o u n t ( b ) 一 。 则生成关联规则b j ( a - 鳓。 问题( 1 ) 是近年来关联规则挖掘算法研究的重点。比较流行的方法是基 于a g r a w a i 等人建立的项目集格空间理论。这个理论的核心是：频繁项目集 的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。由于问题( 2 ) 中的相应操作极为简单，因此挖掘关联规则的总体性能由问题( 1 ) 决定。 3 3 遗传算法 3 3 1 遗传算法的产生背景及思想 遗传算法m ( g e n e t i ca l g o r i t h m ，g a ) 的基本思想是基于m e n d e l 的自然 遗传学说和d a r w i n “自然选择和适者生存一的进化论。g a 是一种基于进化 论的优胜劣汰、适者生存、自然选择和物种遗传思想的搜索算法，着重强调 哈尔滨工程大学硕士学位论文 目的性的算法化进化过程。它通过模拟生物在自然界中的生存竞争与遗传变 异等遗传行为，在竞争中得以改进( 或进化) 问题的解，从而求得问题的最 优解或满意解。 3 3 。2 简单遗传算法 3 3 2 1 简单遗传算法的概念 遗传算法m ，( 也译为基因算法) ，是一种是模拟生物进化过程中优胜劣 汰规则和群体内部染色体信息交换机制的一种处理复杂优化问题的新方法。 它是在2 0 世纪6 0 年代中期，由美国密执安大学的h o l l a n djh 教授首先提出， 并随后和他的学生们发展起来的t a 6 ，。h o l l a n d 的功绩在于他开发了一种不仅可 描述交换，也可描述突变的编码技术，这便是最初的遗传算法，现在通常称 之为简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m ，s g a ) 或标准遗传算法。 3 3 2 2 简单遗传算法的内容 s g a 由四个部分组成：编码机制、控制参数、适应度函数、遗传算子。 1 编码机制 编码( e n c o d i n g ) 是由问题空间向g a 空间的映射，这是g a 的基础。 g a 不对研究对象直接讨论，而通过某种编码机制( e n c o d i n gm e c h a n i s m ) 赋 予对象统一特定的、按一定顺序排成的符号( 字母) 串( s t r i n g ) 。编码问题 中，作为遗传信息传递的载体，符号串代表了染色体，串上每个位置的元素 代表了遗传因子。 编码的主要技术包括m 1 ：一维染色体编码( 包括二进制编码、实数编码、 格雷编码等) 、可变染色体长度编码、多参数映射编码、二倍体、多倍体编 码以及树形编码等。h o l l a n d 模式定理m 嚏议使用二进制编码，但二进制编码 精度不高。双倍体二进制编码比单倍体的动态跟踪能力更强。浮点数编码精 度高，便于大空间搜索，是现在的研究热点。 2 控制参数 g a 的实际操作中，适当确定某些控制参数( c o n t r o lp a r a m e t e r s ) 的值可 以提高选优的效果。这些参数包括： 2 3 哈尔滨工程大学硕士学位论文 ( 1 ) 串长，即字符串所含字符的个数。在s g a 中，这一长度为常数， 记为定长记为； ( 2 ) 每一代群体大小，也称群体容量，即所包含字符串的个数，记为： ( 3 ) 交换率( c r o s s o v e rr a t e ) ，即施行交换算子的概率，记为p c ； ( 4 ) 突变率( m u t a t i o nr a t e ) ，即施行突变算子的概率，记为尸臌。 用二进制编码时，特定问题解的精度决定了串长工的选择。目前常用的 参数取值范围是：n = 2 0 2 0 0 ，肛0 5 1 0 ，p = o - o 0 5 m 1 。若群体容量较大， 例如n = 1 0 0 ，通常取肛0 6 ，厶= 0 0 0 1 ；若群体容量较小，例如n = 3 0 ，通常 取肛0 9 ，厶= 0 0 1 t 。在s g a 中，这些参数一般是不变的。许多学者认识 到这些参数是需要随着遗传进程而自适应变化的，这种具有自组织性能的遗 传算法具有更高的全局最优性、鲁棒性和效率。此外，还包括遗传的“代 数，或其他可确定中止繁殖的控制参数等m ，。 3 适应度函数 优胜劣败是自然进化的原则。对于优化问题，适应度函数即目标函数。 引入适应度函数( f i t n e s sf u n c t i o n ) 的目的也就在于可以对个体进行评估比 较，确定优劣程度。适应度函数是选择操作的依据，是评价个体适应环境的 能力，遗传算法的性能直接受其影响。因为对适应度函数唯一的要求是：结 果为非负值，所以适应度函数是由目标函数变换而成的。这就使得遗传算法 能够应用于不连续、不能求导的情况，大大地增加了其灵活性和适用性。这 种对目标函数值域的某种映射变换称为适应度的尺度变换，采用尺度变换可 以克服未成熟收敛和随机漫游现象m ，。常用的适应度函数尺度变换方法主要 有线性变换、幂函数变换和指数变换。 4 遗传算子 最重要的遗传算子( g e n e t i co p e r a t o r ) 有三种：选择( s e l e c t i o n ) 、交 换( c r o s s o v e r ) 、突变( m u t a t i o n ) 。 ( 1 ) 选择算子 也称复制( r e p r o d u c t i o n ) 算子，是用来确定进行交换的个体，以及被选 择的个体将产生的子代个体数目的。其作用是根据个体的优劣程度决定它在 下一代群体中是被淘汰还是被复制。通常，选择操作将使适应度大( 即优良) 的个体有较大的生存机会，而适应度小( 即低劣) 的个体继续生存的机会也 2 4 哈尔滨工程大学硕士学位论文 就相对较小。 。 实现有效的选择有很多方式，常用的方法有m 。： 适应度比例方法( 轮盘赌或蒙持卡罗选择) 。是指各个体的选择概率 和其适应度值成比例，即适应度为石的个体以= i , e 六的概率生存( 其 中分母为父代中所有个体适应度之和) 。s g a 采取的是适应度比例方法； 最佳个体保存方法。是把群体中适应度最高的个体不进行配对交叉直 接复制到下一代中。此方法一般和其它方法结合使用； 排序选择方法。是指在计算出各个体的适应度值后，根据适应度值的 大小对群体中个体排序，最后再把事先设计好的概率表按序分配给各个体， 作为个体各自的选择概率。所有个体按适应度值大小排序，选择概率和适应 度无直接关系，仅与序号有关； 联赛选择方法。其操作思想是，从群体中任意选择一定数目的个体( 称 为联赛规模) ，其中适应度最高的个体保存到下一代。这一过程反复执行， 直到保存到下一代的个体数达到预先设定的数目为止； 排挤方法。采用该方法时，新生成的子代将替代或排挤相似的旧父代 个体。该方法可以提高群体的多样性。 ( 2 ) 交换算子 交换是指对两个父代个体的部分结构进行替换重组来生成新个体的操 作。在串空间中进行有效的搜索，组合出新个体，同时降低对有效模式的破 坏概率是交换操作的作用与目的。交换操作是在g a 中起核心作用并区别于 其它进化算法的重要特征。 常用的交换操作方法m 唷单点交换( 在个体串中随机设定一个交换点) 、 两点交换、一致交换( 通过设定屏蔽字来决定新个体中的基因继承两个父个 体中哪个个体的对应基因) 、二维交换、树结构交换、部分匹配交换、顺序 交换和周期交换等等。单点交换( s i n g l ep o i n tc r o s s o v e r ) 是s g a 使用的交 换算子。首先从群体中随机取出两个串，串长设为；然后随机确定交换点， 它的取值是从1 到l - 1 间的正整数；最后将两个串交换点后的部分互换，重 新得到两个新串。得到的新串再和原来的串( 亲本) 进行比较，保留适应值 最大的两个。 哈尔滨工程大学硕士学位论文 ( 3 ) 变异算子 进行交换后，可进行变异。变异操作是改变群体中某个个体串的某些基 因位置上的基因值。在s g a 中，变异操作即为o 与l 互换：0 突变为1 ，1 突变为0 。 变异算子有很多种m ，如基本变异算子( 对群体中的个体码串随机挑选 一个或多个基因位置，并对这些基因位置的基因值做变动) 、逆转算子( 从 个体码串中随机挑选两个逆转点，然后将两个逆转点间的基因值以逆转概率 尸逆向排序) 、自适应变异算子( 与基本变异算子的操作类似，唯一不同的 是交换概率p c 不是固定不变的，而是随着群体中个体的多样性程度自适应调 整) 等等。 3 3 2 3 模式定理的概念与内容 1 模式定理的概念 h o l l a n d 的模式定理m 圳揭示了种群中优良个体( 模式) 样本数按指数增 长的规律，从理论上保证了遗传算法是一类模拟自然进化的最优化算法。 模式m ，( s c h e m a ) 表示一些具有相似性的模板或超平面。一个模式描述 在某些基因位置具有相似结构的个体编码串的子集。 以二进制编码为例，个体a o ，l 是由字符集 o ，l 中元素组成的字长为 上的二进制字符串，模式h o ，1 ，+ l 是由字符集 o ，1 ，幸 中元素组成的字符串。 其中“ 表示通配符，它既可表示字符“l 力，也可表示“o 。如果模式日 中的通配符 被确定的字符所替代，则该字符串就称为日的一个实例， 模式h 的所有实例集合，记为沙( 日) 。例如，设h o ，1 ，木 3 ，则 y ( h = 幸1 幸) = 1 0 l o ，0 11 ，1 1 0 ，1 11 。 模式h 中确定位的数量称为模式的阶，记为o ( h ) 。例如， o ( h = 1 幸0 1 幸) = 3 ，o ( h = 0 1 1 1 伊) = 5 。模式h 中第一个确定位的位置和 最后一个确定位位置之间的距离称为该模式的定义长度，记为8 ( ) 。例如， 8 ( h = 0 1 ) = 5 ，8 ( n = l1 0 0 掌) = 4 ，艿( h = 0 ) = 0 。 2 模式定理的内容 设第t 代种群x ( f ) 中与模式日匹配的样本数为m ( h ，) ，模式日的一个 样本串以概率只= z 以被选择，其中石是个体x ，o ) 的适应值。再假设种 哈尔滨工程大学硕士学位论文 群规模为且初始个体互异，交叉概率为p c ，变异概率为厶，模式长度为。 在选择、交叉与变异作用下，模式h 在第t + l 代的样本数为m ( h ，t + 1 ) ，满 口 匕 m ( h , t + 1 夕m ( h ，t ) ( f ( h ) f ) ( 1 - 8 ( h ) p o ( l - 1 ) 一口( h ) 己) ( 3 一1 ) 1n 式中，f = 吉z ，厂( 日) 是模式的平均适应值，d ( 日) 是模式h 的样本 i = 1 平均模式阶。h o l l a n d 通过式( 3 1 ) 给出模式定理m 。： 遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义 长度，并且平均适应值高于种群平均适应值的模式将按指数规律增长。 模式定理揭示了种群中优良个体( 模式) 样本数按指数增长的规律，从 理论上保证了遗传算法是一种模拟生物进化的最优化算法。 3 4 模拟退火算法 3 4 1 模拟退火算法的基本思想 19 5 3 年，nm e t r o p o l i s 等人提出了模拟退火算法m ( s i m u l a t e da n n e a l i n g a l g o r i t h m s ，s a ) 的思想，后来sk i r k p a t r i c k 等人先后研究发展了s a 算法的 理论，并应用到寻找函数最优解问题上。 s a 算法的基本思想：通过模拟高温物体退火过程的方法，寻找优化问题 的全局最优解或近似全局最优解。 s a 是模拟加热熔化金属的退火过程，寻找全局最优解的有效算法之一。 金属的退火过程中，首先加温熔化，使其分子能够自由运动：然后逐渐降温， 促使其分子形成低能态晶体。如果温度下降得足够慢，金属则会形成最低能 量的基态。 哈尔滨工程大学硕七学位论文 3 4 2 模拟退火算法的描述 1 s a 算法描述 ( 1 ) 选民作为初始状态，令s ( o ) = s o ，同时设初始温度乃令卢0 ； ( 2 ) 令弘z ，以丁和s ，调用m e t r o p o l i s 抽样算法，返回状态s 作为本 算法的当前解，s ，= s ： ( 3 ) 按照一定方式降温，即弘z + 。，其中z + 。 乃，f - f + 1 ； ( 4 ) 检查终止条件，如果满足则转步骤( 5 ) ，否则转步骤( 2 ) ； ( 5 ) 当前解s ，为最优解，输出结果，停止。 2 m e t r o p o ii s 抽样算法描述 ( 1 ) 令k = - o 时，当前解s ( o ) 书，在温度丁下，进行以下各步操作； ( 2 ) 按某个规定的方式根据当前解s ( 七) 所处的状态s 产生一个近邻子 集( s ( 七) ) ，从( s ( 七) ) 中随机得到一个新状态s 作为下一个候选 解，计算能量之差a c = c ( s ) 一c ( s ( 七) ) ； ( 3 ) 如果a c o ，则接受s 作为下一个当前解；否则，以概率e x p ( 一a c t ) 接受s 作为下一个当前解。若s 被接受，则令s ( k + 1 ) = s ，否则 s ( k + 1 ) = s ( k ) ； 。 ( 4 ) 令k = k + l ，检查算法是否满足终止条件，若满足，则转步骤( 5 ) ， 否则转步骤( 2 ) ； ( 5 ) 返回s