（计算机软件与理论专业论文）基于混沌模拟退火的rna二级结构预测的研究.pdf

h 。； k i 独创性声明 1 m y 删1 8 帆0 帆2 m 60 孙2 帆 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 日期：。fl 年角矽 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝导师签名：窒! 查! 丑 日期：劲d 年岁月2 6 日 o ， 丫， t i k t 步的研究方向。 关键词：混沌，模拟退火，r n a 二级结构预测 v；l曩1 丫， r n ai s 也ei n t e r m e d i a t e s y n t h e s i so fp r o t e i n s ，p l a y sa l l a p o p t o s i s ，b i o l o g i c a ld e v e l o p m e n t ，d i s e a s et r i g g e r i n ge r e r n as e c o n d a r y s t r u c t u r ei sa k i n do fs t e m - l o o ps p a c es t r u c t u r ew h i c hf o r m sb yb a s ep a i r i n ga n dn u c l e o t i d ec h a i n s e l f - f o l d i n g t h es t e m - l o o ps t r u c t u r e si nr n as e c o n d a r ys t r u c t u r en o to n l yo nt h e a n a l y s i so fr n a f u n c t i o nb u ta l s oc a l lb eu s e dt op r e d i c tr n at e r t i a r ys t r u c t u r e ， t h e r e f o r e ，r n as e c o n d a r ys t r u c t u r ep r e d i c t i o ni sas i g n i f i c a n tw o r k r n as e c o n d a r y s t r u c t u r ec a l lb ed e t e r m i n e db yt h em e t h o do fp h y s i c a l e x p e r i m e n t s ，b u t i ti s t i m e - c o n s u m i n ga n dc o s t l y s o ，r e s e a r c h e r sp r e d i c tr n as e c o n d a r ys t r u c t u r ew i t h b i o i n f o r m a f i c sm e t h o d st oa c c e l e r a t eu n d e r s t a n d i n go ft h es p a t i a ls t r u c t u r eo fr n a m o l e c u l e sa n dt h e i rb i o l o g i c a lf u n c t i o n s t h i st h e s i sd i s c u s s e ss i m u l a t e d a n n e a l i n g b a s e dr n as e c o n d a r y s 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 n c l u d i n g ： 1 e l a b o r a t e st h ee x p r e s s i o nm e t h o do fr n as e c o n d a r ys t r u c t u r ea n df o r m a l r e p r e s e n t a t i o n ； 2 d e s c r i b e st h ee x i s t i n gr n as e c o n d a r ys t r u c t u r e p r e d i c t i o nm e t h o d sa n d s u m m a r i z e st h e i rc h a r a c t e r i s t i c s ； 3 b a s e do nt h es t o c h a s t i c ，e r g o d i c i t yc h a r a c t e r i s t i c so fc h a o sm a p p i n ga n dt h e o p t i m a lc a p a c i t yo fs i m u l a t e da n n e a l i n g ，t h i st h e s i sp r o p o s e da na l g o r i t h m b a s e do nc h a o t i cs i m u l a t e da n n e a l i n ga l g o r i t h mt h r o u g ht h et e c h n i c a lo f c o n t r o l i n gc h a o t i cs y s t e m st r a c kd e n s i t yt oa d j u s tt h ep o s i t i o nw h e r ef o l d i n g o c c u r s ，u s i n gc o o l i n gs c h e d u l et or e g u l a t et h ea n n e a l i n gp r o c e s s ，t a k i n gr n a s e c o n d a r ys t r u c t u r ef r e ee n e r g ya st h eo b j e c t i v ef u n c t i o nt op r e d i c tr n a s e c o n d a r ys t r u c t u r e t h es i m u l a t i o no b t a i n s6 9 1 2 ，5 5 2 6 8 9 1 9 b a s e p a i rc o r r e c t r a t ef o r p r e d i c t i n gr n as e q u e n c ea q u a t i c u sa s e l l u s ，h a l o a r e u l as a c c h a r o m y c e sa n d c e r e v i s i a em a r i s m o r t u ir e s p e c t i v e l y i ts h o w st h ef e a s i b i l i t yo fa p p l i n gt h ec s a a l g o r i t h mb a s e do np o w e rf u n c t i o nc a r r i e rt op r e d i c tr n as e c o n d a r ys t r u c t u r e f u r t h e r i a b s t r a c t w o r kw i l lb ed o n ei na p e c t so ft e s t i n gf o rl o n g e rr n a s e q u e n c ea n ds t u d i n go ft h e a f f e c t so fp o w e rf u n c t i o nc a r r i e rt ot h eb a s ep a i rc o r r e c tr a t e k e yw o r d s ：c h a o s ，s i m u l a t i o na n n e a l i n g ，r n as 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 i v 、 ； v ；， k k k 聍 目录 目录 第一章绪论1 1 1 生物信息学概述1 1 1 1 生物信息学的定义1 1 1 2 生物信息学的任务2 1 1 3 生物信息学的现状与发展3 1 2r n a 二级结构预测的研究现状5 1 2 1 基于最小自由能的r n a 二级结构预测5 1 2 2 比较序列分析法预测r n a 二级结构6 1 3 论文内容及结构安排7 1 3 1 论文内容7 1 3 2 结构安排7 第二章r n a 二级结构9 2 1r n a 的生物学背景9 2 2r n a 的二级结构1 0 2 3r n a 二级结构的表示方法一11 2 3 1r n a 二级结构的几种表示方法1 1 2 3 2r n a 二级结构形式化定义表示1 1 2 4r n a 二级结构的实验测定一1 4 2 5 本章小结1 4 第三章r n a 二级结构预测方法1 5 3 1 预测结果的评价方法1 5 3 2 基于比较序列分析模型的方法1 5 3 2 1 共变模型1 6 3 2 2 随机上下文语法无关模型1 9 3 3 基于最小自由能的方法2 0 3 3 1 最大碱基配对算法2 0 3 3 2z u k e r 最小自由能法2 1 3 3 3 模拟退火算法2 2 v 目录 3 3 4 遗传退火算法2 3 3 4 方法总结及相关资源2 5 3 5 本章小结2 5 第四章基于混沌模拟退火的r n a 二级结构预测2 8 4 1 幂函数载波的混沌模拟退火算法2 8 4 1 1 初始化2 8 4 1 2 解的产生：3 0 4 1 3 解的更新3 1 4 2 幂函数载波的混沌模拟退火算法的实现3 2 4 2 1 自由能的计算方法3 2 4 2 2 结构变化的研究3 5 4 2 3 实验环境4 4 4 2 4 重要的数据结构与实现4 5 4 3 仿真结果j 4 7 4 3 1 序列的选择：4 7 4 3 2 参数选择4 7 4 3 3 实验结果4 9 4 3 4 与其他工作结果的比较5 4 4 4 本章小结5 5 第五章结论和展望5 6 5 1 论文工作总结5 6 5 2 未来工作展望5 6 至筻谢5 8 参考文献。5 9 v i 训 i ， k 罐 第一章绪 1 1 生物信息学概述 第一章绪论 计算生物学的历史可以追溯到2 0 世纪2 0 年代，科学家们在那时已经开始思 考通过归纳法来分析数据并建立生物学规律。1 9 5 6 年，首次“生物学中的信息理 论讨论会”在美国田纳西州的g a t l i n b u r g 召开，而生物信息学逐渐形成是在2 0 世 纪8 0 年代。随着现代医学和生物学的迅猛发展，特别是在在人类基因组计划 ( h u m a ng e n o m er r o j e c t ，h g p ) 的推动下，产生了海量的生物学数据，这些数据需 要分析、处理，揭示这些数据的生物学意义并充分利用这些数据，在计算机技术 飞速发展的推动下，形成了的包括生物学、计算机信息技术的交叉学科生物信息 学。 生物学观测数据通过生物信息学的处理，可以帮助生物学家理解生命运行机 制并解释生命现象。生物信息学在生物科研、药物开发中都具有广泛的应用价值。 2 1 世纪是生命科学飞速发展的新世纪，生物信息学将是一个非常重要的、极具挑 战性的领域。 1 1 1 生物信息学的定义 生物信息学是用计算机和统计技术对生物信息进行分析，运用计算机算法和 数据库技术辅助生物学研究的学科，生物信息学更是分析生物数据的重要工具。 美国国家生物技术信息中心( t h en m i o n a lc e n t e r f o rb i o t e c h n o l o g y i n f o r m a t i o n ，n c b i ) 2 0 0 1 年将生物信息学定义为：“生物信息学是生物学，计算机 科学与信息技术的交叉学科，生物信息学包括三个重要的分枝学科：开发新的算 法和统计技术评估海量生物信息数据之间的关系：分析和解释包括核苷、氨基酸 序列、蛋白质域和结构在内的各种数据；开发各种加速访问和管理各种类型数据 的工具”。 网络百科全书将生物信息学定义为“运用计算机技术管理生物信息的学科。 特别地，它是开发计算机算法和数据库辅助加速生物学研究的科学。生物信息学 被人类基因工程大量用于人类基因( 大约3 0 亿个碱基对) 测序研究，药物开发中也 大量运用生物信息技术识别新的目标分子”。 电子科技大学硕士学位论文 术语生物信息学、计算生物学和生物信息基础设施常常可以交换使用，生物 信息学包含生物信息的存储，计算生物学则强调计算机算法工具的使用，生物信 息基础设施则是由信息搜集，管理，分析工具，通信网络来支持生物学。因此， 可以将生物信息基础设施看着是生物信息学、计算生物学的基础。 1 1 2 生物信息学的任务 生物信息学任务主要包括如下8 个方面： 1 d n a ，r n a 和蛋白质序列的对比【1 1 。比较序列之间的相似性，目前比较成 熟的算法是被称作s n f i t h - - w a t e r m a n 算法【2 】的动态规划算法，它是解决局 部比对的好算法，但速度较慢。遗传算法【3 l ( g e n e t i ca l g o r i t h m ，g a ) 常被用 于两个以上的多重序列比对，目前，还缺乏快速而又非常有效的多重序列 比对算法。 2 染色体上的基因图谱分析【l 】。基因图谱帮助分子生物学家发现基因组， h g p 的一个主要目标就是绘制一系列清晰描述人类染色体的图表。 3 d n a 序列上基因的发现和启动子的识别。给定基因组序列后，自动识别 d n a 大分子序列上的基因和基因组在序列上的位置或范围，识别起始密 码子、剪切位点和终止密码子是生物信息学的一个难题，这个领域仍有大 量的工作需要做。 4 解释基因表达和微阵列数据。传统观点认为相互作用的基因更可能拥有相 似的表达方式，微阵列产生可以同时测量大量的基因表达水平，生物信息 学工具需要被用于基因表达的解释和微阵列数据的处理。 5 基因控制网络识别。通过d n a 微阵列获得的基因表达数据推断基因管理 网络是生物信息学领域最具挑战性的难题。 6 为研究进化关系构建系统发育树。地球上的所有物种都经历着一个漫长的 进化过程。进化树用于研究物种之间的进化关系。 7 d n a 、r n a 和蛋白质结构的预测与分类。包括二级结构和三级结构的预 测与分类，二级结构对于三级结构的预测起着辅助作用，并可以直接根据 其结构设计药物。 8 基于分子结构的药物设计。基于生物大分子结构进行药物设计是生物信息 学中的极为重要的研究领域，例如，为了抑制某些酶或蛋白质的活性，分 析蛋白质的结构、功能以及与人类疾病之间的关系，在蛋白质分子的三级 2 妒 0 k k 第一章绪论 结构的基础上设计抑制剂分子，作为药物治疗疾病。 1 1 3 生物信息学的现状与发展 2 0 0 3 年4 月1 4 日，人类基因组计划完成【4 】，后基因时代来临。生物信息学 随着人类基因组计划的执行得到迅速发展并已深入到生命科学的方方面面。美国 国家生物技术信息中心( n c b i ) ，欧洲生物信息学研究所( e b i ) ，日本的信息生物学中 心( c m ) 等科研机构相继建立，其目的是进行计算分子生物学的基础研究，构建和 散布分子生物学数据库；随着基因科学和计算机科学的迅速发展，全世界各种生 物信息学的科研机构、组织、生物科技公司、生物制药公司如雨后春笋般涌现， 各种生物信息数据库相继建立，如1 9 7 9 年美国洛斯阿拉莫斯国家实验室建立起 g e n b a n k 数据库，欧洲分子生物学实验室建立了e m b l ，日本建立了国家级的核 酸序列数据库d d b j 等。 目前，我国知名的生物信息学研究机构有北京大学生物信息学研究中心、天 津大学生物信息中心、上海生物信息中心和华大基因组信息中心等。北京大学生 物信息学研究中心建立了多个生物信息相关网站的镜像站点，将国外著名生物信 息中心的信息资源移植到本地服务器，以提高国内用户的访问效率，其主页 h t t p ：w w w c b i p k u e d u o n 聚合了很多生物信息学研究相关的资源。表1 1 所示为 国内几个生物信息学科研机构的链接。 生物信息学研究工作可以加速生物学数据的处理和分析，为生命科学的发展 提供了便利有力的技术支持。2 l 世纪被预言是生物科学的时代，随着人类基因组 计划的各项任务接近完成，有关核酸、蛋白质的序列和结构数据呈指数增长。面 对巨大而复杂的数据，运用计算机技术更加有效管理数据、控制误差、加速分析 过程势在必行。随着后基因组时代的到来，生物信息学研究的重点将逐步转移到 功能基因组信息研究，生物信息学的重要目标在于理解生物学数据和揭示生命本 质。目前，网络上各种生物数据仓库如雨后春笋一般出现，但由于统一的数据描 述规范的缺乏，这些数据仓库相对分散、存于异构的数据库甚至是存在冗余和混 乱的生物学数据。因此，发展集成的生物数据仓库和联邦数据库技术以及发展整 合功能基因组数据分析软件体系都是生物信息学今后重要的发展方向。 在应用研究领域，生物信息学在寻找和分析人类疾病基因、预测基因和蛋白 质的结构和功能方便起着重要作用，其成果可能被在实践应用中，如对人类疾病基 因和动植物基因的结构和功能的研究可以辅助核苷类药物设计为人类疾患的诊治 3 电子科技大学硕士学位论文 开辟全新的途径，或改良动植物的物种生产转基因的蔬菜等。在商业利益的驱使 和各国政府的大力支持下，生物信息学将得到更加广泛，更快速的发展。 表1 - 1 几个国内的生物信息研究机构 机构名称网址说明 包含了多个生物信息资源镜象，涵盖了从单 个基因表达调控到基因组研究、从d n a 序 北京大学生物信 h t t p ：w w w c b i p k 列到蛋白质结构功能、以及文献查询、网络 息中心u e d u c n c h i n e s e 教程等各个方面。承担了在数据库构建、基 因预测、分子模型、蛋白质结构预测分析等 领域的研究项目。 中科院计算所前 主要研究方向： 瞻研究中心生物 h t t p ：w w w b i o i n f基于质谱技术的计算蛋白质学研究 0 o r g e n 基于蛋白质结构的计算蛋白质学研究 信息课题组介绍 基于生物网络的计算蛋白质学研究 h t t p ：t u b i e t j u e d u o n 天津大学生物信研究方向为基因发现与识别，结构预测，膜 息中心 h t t p ：s y n b i o t j u e 蛋白质分类预测等。 d u c n p o r t a l i n d e x h t m l h t t p ：w w w g e n o m参与人类基因组计划，在北京、深圳、香港、 华大基因 i t s c n i n d e x p h p 等地设立研究中心。 复旦大学理论生 h t t p ：t l i f e f u d a n e 致力于原核生物与水稻完整基因组的分析。 命科学研究中心 d u e n 综上所述，生物信息学的许多研究成果可以较快地产业化，成为价值很高的 产品。因此，生物信息学不仅具有重大的科学研究意义，而且具有巨大的经济效 益，发展生物信息学具有重要的现实意义和深远的战略意义。 4 ， ； l 第一章绪论 1 2r n a 二级结构预测的研究现状 p d , i a 二级结构的预测即根据r 2 4 a 序列预测模体( m o t i 0 可能出现在序列上的 位置。基于生物信息学的r n a 二级结构预测方法包括比较序列分析法【5 】、最小自 由能法两大类。2 0 世纪7 0 年代，t i n o c o 等人提出了最小自由能模型【6 】，该模型 假设r n a 自身会折叠成一个具有最小自由能的二级结构，碱基配对的堆积造成 自由能的降低，其自由能值为负值，除碱基对堆积外的其它模体具有正的自由能。 在最小自由能模型的基础上，z u k e r 等人使用动态规划( d y n a m i cp r o g r a m m i n g ，d p ) 的方法来预测r n a 的稳定结构( 或称最优结构) 【7 】。一般认为，在同源的生物分子 中，结构保守性一般大于序列的保守性( 即同源r _ n a 通常具有相似的结构) ，而在 实验数据集中可能有许多序列是一组或几组同源r n a 序列，因此，基于同源序 列的r n a 二级结构预测方法一比较序列分析法【1 9 2 4 ( c o m p a r a t i v es e q u e n c e a n a l y s i s ) 被提出来。 1 2 - 1 基于最小自由能的r n a 二级结构预测 基于最小自由能技术的r n a 二级结构预测思想源于热力学中的稳定结构物 体的自由能最小化原理。z u k e r ，w a t e r m a n 等提出r n a 二级结构中模体可以分为 茎区( s t e m ) 、发夹环( h a i r p i n ) 、内环( i n t e r n a l ) 、凸环( b u l g e ) 、和多分支环 ( m u l t i b r a n c h ) ，可以通过一定的规则计算每个子结构的自由能值，最后r n a 二 级结构的自由能则等于该结构上各模体的自由能之和。根据自由能最小化原理， 可以将r n a 二级结构的预测问题转化为对组合优化问题的求解，研究人员通过 计算r n a 二级结构中茎环结构的自由能作为目标函数，实施问题空间的映射， 通过对目标函数的优化来预测r n a 二级结构。大量实验数据显示，r n a 真实的 二级结构不一定是自由能最小的二级结构【8 】。z u k e r 等人认为真实二级结构可能不 是自由能最小的二级结构，在与最小自由能相差给定阈值范围内的次优结构均可 能是r n a 的真实二级结构。 基于最小自由能的方法包括确定性算法和启发式算法。如文献 9 】提出的基于 动态规划算法为确定性的预测r n a 二级结构的方法，在考虑多分支环自由能的 情况下，算法时间复杂度和空间复杂度分别为o ( n 4 ) 和o ( n 3 ) ，其中行为r n a 序 列长度。文献 1 0 】采用模拟退火算法通过碱基配对或拆分碱基对的方式改变r n a 二级结构，分别以热力学自由能和动力学活化自由能为目标函数，对马铃薯管状 病毒r n a 二级结构进行预测，模拟r n a 二级结构的形成和重排过程。文献【1 1 】 5 电子科技大学硕士学位论文 提出一个基于遗传模拟退火的r n a 二级结构预测方法，对交叉操作后个体执行 模拟退火过程，预测马铃薯管状病毒的r n a 二级结构。 文献 4 3 】提出了一种新的免疫粒子群集成算法，利用免疫机制，在粒子群优 化算法中设计了免疫替换算子，避免粒子群优化算法易陷入局部最优的缺陷，通过 集成技术充分发挥粒子群优化算法的优点，实现协同演化，提高了算法的全局搜 索能力。实验证明了使用免疫粒子群集成算法预测r n a 二级结构的有效性。 文献 4 4 】将随机动力学引入h o p f i e l d 神经网络算法，提出了一种允许自由能 临时升高但最终降低的算法，它能够帮助h o p f i e l d 网络跳出局部最优且找到最优 或次优解，将该方法应用于r n a 二级结构的预测，仿真结果表明具有更优的稳 定性。文献 4 5 改进了h o p f i e l d 网络预测r n a 二级结构的方法，将分类信息引入 h o p f i e l d 算法的初始化，实验结果表明这种改进的有效性。 1 - 2 2 比较序列分析法预测r n a 二级结构 由于r n a 同源序列结构的一致性，通过比较并分析多个同源序列的r n a 二 级结构的预测方法比较序列分析法被提出来。比较序列分析法对多条序列进行互 补碱基的共变联配，在已知序列数据库中搜寻待测序列的相似序列，以推断待测 序列的二级结构。比较序列分析法需要同源序列二级结构作为样本，样本序列与 被测定序列需有相似的二级结构和共同的茎环基本结构单元，因此，样本序列数 量越多，与被预测序列越相近，预测结果越精确【8 】a 按照序列比对与结构预测的先后顺序可将比较序列分析法分为3 类【1 2 】： 1 先序列比对后结构预测方法。假定结构保守性大于序列保守性，其预测 结果强烈依赖于多序列比对的效果，该类方法得到大量的次优结构，而多个次优 结构与真实结构的相关度不能确定，且目前结构比对仍是生物信息学中的一个难 题。 2 结构预测与序列比对同时进行。代表性算法是s a n k o f f 算法，它结合序列 比对和n u s s i n o v 折叠进行循环，该算法对计算资源的需求较高，其时间复杂度为 0 ( n 3 m ) ，空间复杂度为o ( n 2 m ) ，其中1 3 是序列的长度，m 是序列的数量。 3 先预测结构后比对序列。当观察不到序列保守区时，比较适合使用该方 法，它包含了结合了结构信息的多序列比对，然而，如何完美地融合结构信息， 尽量得到效果理想的多序列比对至今仍然没有解决。 目前，基于第一类方法的软件工具有p f o l d l l 3 l 、a l i f o l d r n a f o l d 1 4 】等，基于 6 h 第二类方法的软件工具有d y n a l i 具有m a r n a t l q 等。大量研究实 于r n a 二级结构的实验室测定 的限制，在实践中该方法受到限 1 3 论文内容及结构安排 1 3 1 论文内容 本文研究基于混沌模拟退火的r n a 二级结构预测算法，分析幂函数载波的 混沌映射对于产生r n a 二级结构产生的关系，讨论r n a 二级结构变化的方法与 r n a 二级结构能量的计算方法，幂函数载波的混沌系统取代模拟退火算法中服从 高斯分布的随机数，同时利用m e t r o p o l i s 准则接受适应度较差的个体，有效跳出 局部最优，达到全局最优。采用幂函数载波混沌映射产生初始解，以冷却进度表 控制模拟退火过程，r n a 二级结构自由能做为目标函数，通过三个r n a 序列二 级结构的预测实验，仿真结果表明所提方法是可行有效的。 1 3 2 结构安排 论文的具体安排如下： 第一章绪论首先介绍生物信息学来源，生物信息学的定义及其研究任务、现 状与发展，然后介绍了r n a 二级结构的国内外研究现状，对两大类r n a 二级结 构的预测方法做了概括阐述，最后是本文的内容及结构安排。 第二章介绍了r n a 的生物学背景，r n a 二级结构相关的背景知识，并详细 介绍了r n a 二级结构的定义，表示方法，以及实验室的测定方法。 第三章详细介绍了r n a 二级结构预测的几种方法，包括共变模型预测、随 机上下文无关语法预测、最小自由能预测的几种方法如z u k e r 最小自由能法、模 拟退火算法、遗传退火算法，最后对几种方法进行了总结并给出了一些二级结构 预测相关的资源。 第四章基于幂函数载波c s a 算法的r n a 二级结构预测方案被详细阐述，是 本文的核心，在这部分，提出了基于混沌模拟退火的r n a 二级结构预测算法， 将幂函数载波的混沌系统映入模拟退火算法，并应用于r n a 二级结构的预测， 提出了一种初始化算法，详细分析了新结构产生过程中的2 0 种情况，介绍了最近 7 电子科技大学硕士学位论文 邻自由能的计算方法，实现了基于混沌模拟退火的r n a 二级结构预测算法，讨 论了参数的选择，分析了实验结果，并与r n a 二级结构预测工具r n a s t r u c t u r e 4 5 进行了性能的比较。 第五章对全文进行了总结并指出工作中的不足，及未来的研究方向。 弋 l 0 ， 糖为骨架链，腺嘌呤( a d e n i n e ，a ) ，鸟嘌呤( g u a n i n e ，g ) ，胞嘧啶( c y t o s i n e ，c ) 和尿嘧啶( u r a l i c ，切四类碱基通过磷酯键缩合而成的链状生物大分子。r n a 参与 蛋白质的合成，在细胞分化凋亡、生物发育、疾病发生等方面起着重要作用。 碱基g 、c 和a 、u 能通过氢键联接为互补碱基对，其中，g 、c 之间能形 成3 个氢键，a 、u 之间可以形成2 个氢键，这两种碱基配对成为w a s t o n - c r i c k 配对。除此之外，还有一种非典型摆动配对( w o b b l eb a s ep a i r s ) 存在，即碱基g 、 u 形成配对，g 、u 在热力学上有与典型的w a s t o n - c r i c k 配对一样的稳定性，结 构的稳定性与氢键的个数有着直接的联系，一般来说，氢键的个数越多，缩合成 的碱基配对越稳定，因此，在稳定性上g c a u g u 3 4 1 。几个、几十个、甚至成 千上万个a 、c 、g 、u 碱基以特定顺序排列形成多核苷酸序列。 r n a 作为遗传信息的中心媒介参与中心法则中的转录d n a 上的遗传信息， 并翻译这些遗传信息，合成相应的蛋白质，参与这一过程的r n a 可以称为编码 r n a 。近年来，研究人员发现，某些r n a 具有催化性质，或直接承载着各种重要 生物化学功能，这类r n a 被称为非编码r n a 3 5 , 3 6 】。掌握r n a 结构知识，为研 究开发靶向核糖体或病毒r n a 的药物建立了基础。许多非编码r n a 结构上的保 守性要大于它在序列上的保守性，认识它们的结构，不仅可以帮助我们准确详细 地理解各类r n a 在细胞中的运作机制，还可以为在基因组中寻找新的非编码 r n a 基因提供帮助。 r n a 分子具有三类结构：一级结构是核苷酸的序列；二级结构是碱基配对与 核苷酸链折叠而成的茎环空间结构，如图2 - 1 所示；三级结构是二级结构的结构单 元通过氢键的长程作用或双螺旋区的成核作用折叠而成的空间构型。r n a 的生物 学功能与其特定的结构紧密相关，例如对r n a 结构知识的掌握为研究开发靶向 核糖体或病毒r n a 的药物建立基础。 目前，基于r n a 一级结构预测r n a 三级结构仍是生物信息学难题，而r n a 二级结构中的茎环结构不仅可用于分析r n a 功能，还可用于预测r n a 三级结构， 9 电子科技大学硕士学位论文 因此，r n a 二级结构预测具有重要意义。 2 2r n a 的二级结构 r n a 二级结构是a u 、g c 、g u 三种碱基配对与核苷酸链折叠而成的茎环空 间结构，可以分为茎区、发夹环、内环、凸环、多分支环等子结构，这些结构单元 可称为r n a 二级结构的模体。 现竭啦b o p 鲴 m i 啦b o p 图2 - 1r n a 二级结构 茎r x ( s t e m ) 是由连续的碱基配对相互堆积而构成，见图2 1 。 发夹环( h a i r p i nl o o p ) 是两端端邻接茎区的一段连续序列，因其形状与发夹相 似，所以称之为发夹环，见图2 1 。 ag - g 莨善童 图2 - 2 凸环、自由单链示意图 两个茎区之间的未配对碱基序列构成内环( i n t 耐o r l o o p ) ，见图2 1 。如果两个 l o 第二章r n a 二级结构 茎区有一边相邻，在平面结构图上，其另一边往外凸出，因此，这样则构成的环 形象地称之为凸环( b u l g el o o p ) 示意图见图2 2 。 多分支环( m u l t i - b r a n c h e d l o o p ) 是由3 个或3 个以上茎区构成的环，见图2 1 。 r n a 序列两端没有形成配对的单链叫做自由单链( u n s t r u c t u r e ds i n g l es t r a n d ) 。 示意图见图2 2 。 由于碱基配对的氢键力对结构的稳定性起促进作用，所以，茎区的自由能一 般来说是负值，而各种环区的形成则是结构中的不稳定因素，其自由能值大多为 正值。本文使用的自由能参数将在4 2 1 节中详细介绍。 2 3r n a 二级结构的表示方法 2 3 1r n a 二级结构的几种表示方法 除图2 1 所示r n a 二级结构的平面结构图表示法外，还有l i n e a rf e y m a n 、 c i r c u l a rf e y m a n 、d u a lg r a p h 、d o tp l o t 等r n a 二级结构的表示方法，见图2 3 。 2 3 2r n a 二级结构形式化定义表示 r n a 序列表示为碱基序列r = ，口，c ，g ，叨，其中盯表示碱基数 目，为靠近5 端( 起始端) 碱基，为靠近3 端( 终止端) 碱基，r n a 二级结构如 图2 - 1 所示。 定义2 - 1 【l 】：如果k n a 序列r 存在子序列r 。= + 小。和r ：= 0 一一。+ l ， 其碱基依次互补配对，即满足( ，0 ) 似，( u ，么) ，( g ，c ) ，( c ，g ) ，( g ，( u ，g ) ) ， 1 i ，以，j i 3 ，则序列r 。和足构成茎区j ( f ，j ，k ) ，其中，f 和，分别表示 茎区s 在序列r 中5 端的起始位置和3 端的结束位置，k 表示茎区长度，如图2 4 所示的茎区表示方法。 定义2 2 1 1 1 ：给定茎区j 。( f 。，j ，曩) m s ：( f ：，以，如) ，若茎区s 。与j ：不重叠且不交 叉，即满足以下条件： 一一一一一一 一 一一一 图3 - 1 共变信息与共变模型t 2 2 】 大量研究实验表明，比较序列分析预测砌叮a 二级结构是效果较好的方法， 其预测结果的正确率仅次于实验室测定的砒妊二级结构，它还适用于带假结的 预测和三级结构的预测。但其不足之处在于它依赖于已有序列的先验知识需要一 定数量的序列的样本，并且假定这些序列应该具有一致的二级结构和一些共同的 基本结构单元，对于小样本的序列或者序列来源差异很大其比较结果就不大可靠 了，它的另一个不足在于序列联配耗费大量的计算机时间和空间资源，它的这两 个不足之处限制了它在某些情况下的应用。 3 2 1 共变模型 共变模型实际上就是隐马氏模型( 2 3 1 ( h i d d e nm a j k o vm o d e l s ，h m m s ) i 拘- - 种推 广，可以看作生成一组r n a 序列簇的代表序列的概率机器，但共变模型引入了 分叉和描述共变配对状态。 1 6 第三章r n a 二级结构预测方法 uc ug 5 。e gl oe gl o a u ： a 摹c u j 重_ 童1 5 s 主 3 _ u 一 计- 2 32 0 ： ， e2 3 髟 u a 瓣 图3 - 2 描述r n a 二级结构的有序树2 2 】 一个r n a 的共变模型可以用一棵如图3 2 所示的有序树( o r d e r e dt r e e ) 来表示。 树上始端、末端和分叉结点为哑元，树的每个分支表示一段茎环结构，分支上的 结点表示配对的碱基对或未配对的单链碱基。有序树不仅表示多序列联配的二级 结构，对该树进行一次前序遍历还可以重新得到其一级序列。假设有序树上的非 哑元结点表示多序列联配中的列而不是某单条序列的一个碱基，则有序树可以表 征一簇r n a 序列。a 、c 、g 、u 四种碱基两两配对，加上a 、c 、g 、u 四种碱 基的单链，每一个结点共有2 0 种可能的符号出现，某种符号出现的概率称着符号 发生概率( s y m b o l e m i s s i o np r o b a b i l i t i e s ) 。将这些符号分为“匹配 态、“插入 态、 “删除”态等状态，则有从一个结点到下一个结点的状态转移概率( s t a t et r a n s i t i o n p r o b a b i l i t y ) 。 s f d , y ( y = m a t p ) = m a x s t + l j 一1 ，y 。时+ l o g t ( y h 职c1 ) ，) + l o g p ( x f ，暂1 ) ，) ) s t j , yp = m a t l ，i n s l ) = 罂a x 溉+ u ，y 。+ l o g t ( y n 簖ci y ) + l o g p ( x d y ) ) j s t j ( y = m a t r ，i n s r ) = 乎a x ( & j 一1 ，) ，埘愀+ l o g t ( ) ，。e x ti ) ，) + l o g p ( x ji y ) ) ，n t 盯 s t j , y ( ) ，= d e l ) = m 竺 s t j 。时+ d 日丁( 眦i y ) ) ，n x t s t j , y ( y2b i f u r c ) 2f l m 9 m a x d 茸 s t ，m f d y l e 厂t + f d + 1 d , y r t a t ) 其中m a t p 、m a t l 、m a t r 属于匹配态状态，i n s l 、i n s 属于插入状态， 1 7 电子科技大学硕士学位论文 d e l 属于删除状态，b i f 属于分叉状态，b e g 属于开始状态，他们构成了有序树 中所有结点状态的指标集，m a t l 和m a t r 分与i n s l 和i n s r 结合起来可以把 单链碱基表示成与一个插入的空位相配对的匹配状态。丁( 。nl y ) 是从状态y 到状 态眦的转移概率，p ( 旎，西i y ) 表示在状态y 下出现符号恐，蕾的概率。初始值设 定量，f ，y ，最+ i , l y = d ，净j m 其它全部赋值为负无穷，然后从f 可+ 巧= j 开始一直计 算到i = l j = n 。 对于一簇r n a 序列，确定了有序树各结点之间的一组稳定的状态转移概率， 这组r n a 序列的共有的二级结构模型也就可以确定了。为了找到表示这簇r n a 序列二级结构的“最好的”树，如图3 - 3 所示，共变模型方法分三个步骤来完成： 多序列联配、共变模型建立和参数修正，这三个步骤是一个相互影响，逐步优化 的过程。 图3 - 3 共变模型的训练过程【2 4 】 为了尽量利用联配中两列之间能否形成一致的w a t s o n - c r i c k 互补配对的共变 信息，引