（应用数学专业论文）rna的二级结构.pdf

摘要 对r n a 结构与功能的研究是当今生物信息学一个非常重要的课题，对r n a 自身功能的认识在今已经得到了很大的拓展和深入，而研究它更可以作为研究蛋 白质结构与功能以及d n a 序列中基因信息的突破口 一个r n a 序列可以看作是一个有四个字母的字母表n = a ，c ，g ，c ，) 上的 字( w o r d ) ，而r n a 二级结构是自由基( f r e e b a s e ) 和基对a u 和a g 组成 的在一定程度上，r n a 二级结构经过处理后都可以转化为线性序列因此， 组合学和统计学的工具和方法可以在研究生物序列和生物结构上发挥很大的作 用同样我们可以用几何方法来表示生物序列和二级结构，几何拓扑和群论也发 挥了很大的作用 目前所有有关r n a 二级结构的预测算法要预测出所有序列的二级结构仍然 很困难，本文系统介绍了从上世纪7 0 年代以来发展至今的各类r n a 二级结构 预测算法，从对r n a 结构预测方法的追溯和跟踪，对当今r n a 研究的进展和 形势做了个总结并且应用组合计数的技巧解决了一类r n a 二级结构的计数 问题 本文主要内容包括以下几方面： 首先介绍了一些分子生物学中的基础知识大多数后面要用到术语和基本概 念都在这里做了简要的介绍 接着详细介绍了r n a 二级结构预测的一些相关知识如：方法的发展、基 本原理、局限性等并介绍了目前几种典型的r n a 二级结构预测算法 最后应用组合计数的技巧解决了一类r n a 二级结构的计算问题 关键诲r n a 二级结构；递归公式；发生函数 r n a s e c o n d a r ys t r u c t u r e a b s t r a c t t h er e 8 e e r c ho fr n as t r u c t u r ea n df u n c t i o n 氆av e r yi m p o r t a n tq u e s t i o ni n b i o n f o r m a t i c st o d a y a tt h es a m et i m ei t h a sr e c e i v e dal o to fd e v e l o p m e n ta n dd e e p g o i n g i tc a n s e r e v ea sab r e a k t h r o u g ht ot h er e a s e a c ho fp r o t e i ns t r u c t u r e ，f u n c t i o n a n d g e n e t i c a 丑a s e q u e n c e c a nb ei d e n t i f i e dw i t haw o r do v e rt h e a l p h a b e tn = a ，gg ，u w h i l et h es e c o n d a r ys t r u c t u r eo f r ai sas e to f f r e eb a s e sa n d p a i r sw h i c h f o r m sb o n d s b e t w e e na ua n dc - g i ns o m ec o n s i d e r a b l ee x t e n t ，t h es e c o n d a r ys t r u c t u r eo f a n a c a nb er e d u c e di n t ol i n e a rs e q u e n c e s s ot h et o o l sa n dm e t h o d si nc o m b i n a t o r i c sa n d s t a t i s t i c sw i l lp l a yi m p o r t a n tr o l e si ns t u d l n gl i n e a rs e q u e n c e so fb i o m o l o c u l a ru n i t s a l s o ，w ec a np r e s e n tt h eg e o m e t r i cr e p r e s e n t a t i o no f b i o l o g i c a ls e q u e n c e sa n d s t r u c t u r e s s ot h eg e n o m e t r i ct o p o l o g ya n dg r o u pt h e o r ya x ei m p o r t a n ta l s o a tp r e s e n ti ti sv e r yd i f f i c u l tt op r e d i c ta l lt h er n a s e c o n d a r ys t r u c t u r e s t h i s p a p e rd e s c r i b e sr 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 nm e t h o d s f r o m1 9 7 0 t ot h i sd a yi n a s y s t e m a t i c w a ys o m e t r a c i n g b a c k a n d f o h o w i n g t h e t r a c k s o f p r e d i c t i o n m e t h o d s t h e a u t h o rm a d eas u m m a r yo fr 且r e s e a r c hp r o g r e s sa n ds i t u a t i o nw h i l eae n u m e r a t i o n p r o b l e mo fr as e c o n d a r ys t r u c t u r ei s s t u d i e dw i t ht h em e t h o do fc o m b i n a t o r i a l e n u m e r a t i o n t h em a i nc o n t e n t so ft h i sp a p e r el i s t e da sf o l l o w s ： i nc h a p t e r2 ，w ei n t r o d u c es o m eb a s i ck n o w l e d g eo fm o l e c u l a rb i o l o g y m o s to f t h et e r m sa n d c o n c e p t su s e di nt h i sp a p e re r ee x p l a i n e db r i e f l yh e r e i nc h a p t e r 3 ，s o m e i n f o r m a t i o no f t h er n a s e c o n d a r ys t r u c t u r ei si n t r o d u c e d ui n d e t a i l ，s u c h d e v e l o p m e n to f m e t h o d 、c a r d i n a lp r i n c i p l e 、l i m i t a t i o n sa n d 8 0o n t h e n w ei n t r o d u c es o m et y p i c a lp r e d i c t i o na l g o r i t h m so ft h e 矗as e c o n d a r ys t r u c t u r e s i nc h a p t e r4 ae n u m e r a t i o np r o b l e mo f 兄as e c o n d a r ys t r u c t u r ei ss t u d i e dw i t h t h em e t h o do fc o m b i n a t o r i a le n u m e r a t i o n k e y w o r d s ：r n a s e c o n d a r ys t r u c t u r e ；r e c u r s i o nf o r m u l a ；g e n e r a t i n gf u n c t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及取 得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或其他单位的 学位或证书所使用过的材料与我一同工作的同志对本研究所做的贡献均已在论 文中做了明确的说明并表示了谢意。 作者签名：番敏日期：趁2 三! 7 l 前言 1 1 引言 随着人类基因组计划( h g p ) 实旖的进一步深入，生命科学已经步入后基因 时代基因和蛋白质已经成为现代生命科学的主要研究对象过去，生物科学家 们研究单个基因或蛋白质，现在和将来，科学家们将着重研究d n a 序列信息， 蛋白质结构信息，以及它们之间的相互作用破译每一水平的生物信息提出了与 基因或蛋白质有关的统计和组合数学问题生物信息的急剧增长也带来了对计算 机科学的挑战为此，计算分子生物学和生物信息学便应用而生 广义地说，生物信息学是对生物信息的获取、加工、储存、分配、分析、和 释读、并综合运用数学、信息科学、计算机科学、系统科学和生物工具，以达到 理解数据库中各种数据的生物学含义的目的与此对应，生物信息学具有三方面 的科学基础：首先，它需要发达的，复杂的、可相互交流的数据库系统；其次， 生物信息学需要强有力的创新算法和软件来获得持续的发展；最后也是最重要的 是生物信息学需要个大规模、高通量的生物学研究方法和平台技术，这些技术 既是生产生物信息数据的主要方法，又是在利用生物信息分析结果的基础上进一 步获取或验证生物学知识的关键 生物信息学是计算分子生物学的“孪生”学科人们常常不加区别的使用这 两个学科名称严格来讲，生物信息学还包括对各种生物信息存储和查询的研 究 计算分子生物学( c o m p u t a t i o n a lm o l e c u l a rb i o l o g y ) 是一门崭新的交叉学科， 主要是研究分予生物学应用上具有计算复杂度的问题，它吸引了许多计算机科学 家，分子生物学家，数学家，物理学家投入研究计算分子生物学的研究对象是 与基因和蛋白质序列有关的组合和计算问题，计算分子生物学的主要课题有：序 列组合，序列分析，生物信息资料库，基因认定，种族树的构建以及分子结构预 测等 分子结构预测包括td n a ，r n a ，蛋自质及基因预测等随着对r n a 的研 r n a 的= 级结构 究逐步深入，人们再也不象过去那样，仅仅把r n a 看成d n a 到蛋白质之间的 一种信息传递中介r n a 正在从人们眼中简单的、线性的、功能单一的形象演 变成今天种类多样，结构复杂，功能特异的新形象，并且逐渐在中心法则中取得 了与d n a 和蛋白质同等重要的地位，尤其是上世纪8 0 年代中期，对于具有催 化陛质的r n a 的惊人发现，使人们得到启发，提出了原初生命是一个“r n a 世界”的假说 1 】现在，r n a 的功能正得到人们的日益关注而功能与结构是 密切相关的所以，r r n a 在核糖体中的催化机制和构成作用，m r n a 前体在 转录后水平的选择性剪接，m r n a 自身的稳定性及其翻译效率，s n r n a 与蛋 白质的相互作用以及作为信号识别颗粒的机制，r n a 酶对t r a 和r r n a 的 转录后加工，反义r n a 在翻译水平上的调控作用等等一系列问题都在促使着人 们对r n a 的具体结构更深一步的了解，力图从其结构上来阐明，发掘其功能， 搞清楚r n a 的具体结构，不仅能使我们更细致地了解各类r n a 在细胞中 的运作机制，而且还可以为在基因组中寻找新的基因，以及为提高蛋白质结构预 测的准确率提供帮助，更为重要的是，对于r n a 结构知识的掌握，为研究开发 靶向核糖体或病毒r n a 的药物提供了广阔的前景。目前，这一领域已经引起了 越来越多的重视，某些r n a 二级结构的折叠算法已经被广泛用于药物设计的研 究 r n a ( 或蛋白质) 这样的一个生物分子实际上具有三维结构由于这个结构 决定了生物分子的功能，理解生物分子的空间结构便成为分子生物学的最重要的 目标由于r n a 分子具有降解速度快，难以结晶等特点，故通过x 射线结晶衍 射和核磁共振确定生物分子的三维结构很不容易，这样费时费力还代价高昂，虽 然测得的结果比较精确可靠，可是面对当前大量的生物序列，这种方法显然并非 总是可行的，这与确定生物分子的一级结构( 如r n a 中的碱基和蛋白质中的氨 基酸) 的相对容易性形成了鲜明对照，其后果是形成目前的序列知识与结构知识 之间的鸿沟如我们已知道几千种蛋白质的序列，但仅知道几百种蛋白质的三维 结构，且该鸿沟每年都在不断的扩大 在1 9 6 0 年，f r e s c o 等提出了第一个r n a 二级结构预测算法，论述了r n a 二级结构的基本特征和预测的基本原理，如：要求螺旋区长度在4 b p 以上，螺旋 区长度和环区碱基数之间要满足一定关系等r n a 二级结构是由r n a 单链自 身回折而形成部分碱基配对和单链交替出现的茎环结构碱基互补配对形成的 连续双螺旋区域称为茎区，而不形成互补配对的单链结构称为环，依据形态的不 同环又可分为发夹环，内环，膨涨环和多分支环此后，各种r n a 二级结构预 测算法不断涌现，较为著名的方法有；碱基最大配对方法，基于螺旋区所有可能 2 大连理工大学硕士学位论文 组合的r n a 二级结构预测和z u k e r 极小化自由能方法等，并编写了程序，预测 了许多r n a 分子的二级结构，不过许多预测结果与试验结果常有出入，特别是 r n a 大分子和带假结的r n a 分子的二级结构本文我们就应用组合计数的技 巧考虑了r n a 二级结构的计数问题 1 2 论文的结构安排 鉴于r n a 二级结构在r n a 研究以至整个计算分子生物学中的重要地位， 以及目前研究状况，本文就此开展了专门的研究 首先，在第二章我们介绍了一些分子生物学中的基础知识并简要介绍了后 面章节中要用到的部分术语和基本概念 接着，在第三章中详细介绍了r n a 二级预测的一些相关知识如：方法的 发展、基本原理、局限性等并介绍了目前几种典型的r n a 二级结构预测算法 最后，在第四章中应用组合计数的技巧解决了类r n a 二级结构的计算问 题 3 2 分子生物学的知识概论 生命的基本单位是细胞，它是由细胞膜、细胞质和细胞核三者组成的遗传信 息储存在细胞核中，人的细胞核含有2 3 对染色体，染色体包含d n a ( 脱氧核糖核 酸) 和蛋白质、d n a 经螺旋、扭曲、折叠等压缩后与蛋白质一起组成染色体 d n a ，r n a 和蛋白质都是由更小的单元组成的无分支的线性聚合体大分子 对于d n a ，这些单元是a ( 腺嘌呤) 、g ( 胞嚏呤) 、g ( 鸟瞟呤) 和t ( 胸腺嘧呤) 四种 核苷酸残基；对于r n a ，这些单位是以、g 、g 和矿( 尿嘧呤) 四种核苷酸残基； 对于蛋白质，这些单位是a ( 丙氨酸) 、c ( 半胱氨酸) 、d ( 天冬氨酸) 等2 0 种氨基酸 残基在相当大的程度上，d n a ，r n a 和蛋白质分子化学性质编码在这些基本单 元的线性序列( 本原序列) 中 2 1 d n a ，r n a 和蛋白质 d n a ( d e o x y r i b o n u c l e i ca c i d ) 是遗传特征的基础，它是由核苷酸小分子生成 的聚合物核苛酸有四种，可以用四种基来区分他们四个基分别是a ，c ，g ，t d n a 分子可以看成是四个字母字符集k = a ，gg ，研上的词，d n a 分子是 有方向的，左端通常记为5 ，另一端记为3 d n a 蕴含的复制机制的关键特征是碱基互补即a 和t 配对，g 和g 配 对这种配对是由于氢键作用原理是d n a 单个链( 按5 到3 的次序) 5 agtgaetgg3 与相反方向写的互补的链配对 5 1actgactg jflffjii 3 。tgactgac 5 3 5 c i g 墨盟墨笪三堡箜塑 _ d a 分子是双链结构两条链缠绕在一起形成双螺旋，此著名的双螺旋( d o u - b l eh e l i x ) 结构是由j a m e sw a t s o n 和n a l t c i sc r i c k 在1 9 5 3 年发现的这种碱基互 补配对的机制使得d n a 在细胞中得以复制三维结构是螺旋状，下面图指出这 些字母或基是附在个线上或骨架上注意，标明氢键的杠删去了为准确地看 这个图，把它想象为两个边是对应骨架的缎带拧成一个螺旋状如下图： r n a ( r i b o n u c l e i ca c i d ) 是具有重要生物学功能的另一种核酸，其含量在原核 细胞中约占6 ，在真核细胞中约占1 1 r n a 分子与d n a 分子很相似，但在 组成和结构上也有一些重要的不同在r n a 分子中，核糖取代了d n a 分子中 的2 i 脱氧核糖另外，胸腺嘧呤t 被u 取代了，u 与t 一样能够与a 配对 r n a 分子并不形成双螺旋有时我们可以看到r n a - d n a 杂交双螺旋此 外，r n a 能够通过碱基互补与同分子的其他部分结合r n a 的三维结构远 比d n a 复杂d n a 与r i g a 的另一个不同是，d n a 本质上仅有一个功能， 即编码信息，两在细胞中有不同的r n a ，各自行使不同的功能 r n a 的种类主要有核糖体r n a ( r r n a ) 、转移r n a ( t r n a ) 以及信使r n a ( m r n a ) 它们的主要功能是参与蛋自质的生物合成近年来发现的反义r n a 、 具有催化作用的z n a ( r i b o z y m e ) 、细胞核小分子r n a ( s n r n a ) 、核仁小分子 r n a ( s n o r n a ) 等亦都具有重要的生物学功能和广阔的应用前景 在各种r n a 链中，除u 、c 、a 、g 四种基本核苷酸外。还含有多种 稀有核苷酸( 碱基被修饰) ，其中t r n a 含量最高，约占其总核苷酸数的5 一2 0 ； r r n a 次之，含量约为0 6 1 7 ；m r n a 中含量最少或者不含稀有核苷酸 生物体的大部分物质是各种各样的蛋白质，他们既是工作部件，又是组成 原料蛋白质包括很多种，结构蛋白质是组织的构成单元，酶是化学反应的催化 剂蛋白质的其他功能还包括氧气输送和抗体防御等 这种非常重要的大分子是由氨基酸( a m i n oa c i d ) 的分子序列组成的自然界 之中发现了2 0 种不同的氨基酸这些单元是a ( 丙氨酸) 、g ( 半胱氨酸) 、d ( 天 冬氨酸) 、e ( 谷氨鳓、f ( 苯丙氨酸) 、g ( 甘氨酸) 、日( 组氨酸) 、j ( 异亮氨酸) 、 6 盔垄堡三查兰堡主堂鱼堡壅 耳( 赖氨酸) 、三( 亮氨酸) 、m ( 甲硫氨酸) 、( 天冬酰氨酸) 、p ( 脯氨酸) 、q ( 谷 氨酰氨酸) 、矗( 精氨酸) 、s ( 丝氨酸) 、t ( 苏氨酸) 、y ( 颉氨酸) 、( 色氨鳓和 y ( 酪氨酸) ，这是蛋白质种最常见的2 0 种，另外，还有几种非标准的氨基酸- 在蛋白质中，氨基酸通过肽键相连因此，蛋白质是多肽链肽链使得每个 蛋白质都有一个骨架( b a c k b o n e ) ，在骨架的一端是一个氨基酸，另一端是一个羧 基我们因此可以区别多肽链的两端，并给它定一个方向，习惯上多肤始于氨基 ( n 端) ，止于羧基( c 端) 蛋白质并不仅仅是氨基酸残基的线性序列，这种序列称为一级结构( p r i m a r y s t r u s t u r e ) 蛋白质实际上在三维空间中折叠，形成二级结构( s e c o n d a r ys t r u c t u r e ) 、 三级结构( t e r t i a r ys t r u s t u r e ) 和四级结构( q u a t e r n a r ys t r u c t u r e ) 因为蛋白质的三 维结构非常复杂，而且，蛋白质的三维结构与其功能相关，因此确定蛋白质的折 叠或三维结构是分子生物学的一个重要领域 d n a 分子的重要性在于，机体中合成r n a 和蛋白质的信息编码于d n a 分子中基于此，d n a 有时被称为“生命蓝图”每一个细胞都有几个非常长的 d n a 大分子，每一个这样的分子称为染色俸( c h r o m o s o m e ) d n a 中仅有一部分 连续的片段编码构建蛋白质的信息，而且其它部分并不编码蛋白质信息每一种 不同的蛋白质仅对应一段d n a 序列，该段序列称为基因( g e n e ) 如前所述，蛋白质是氨基酸链因此，确定蛋白质仅需确定其所含的每一个 氨基酸，这正是基因所要做的，他用三联体核苷酸编码每一个氨基酸每个三联 体核苷酸称为密码子( c o d o n ) 三联体核昔酸与氨基酸之间的对应关系称为遗传 密码( g e n e t i cc o d e ) 见表i 1 7 r a 的二级结构 表i 1 氨基酸的遗传密码 r a b l ei 1g e n e t i c - c o d e fsyc u 丙氟酸丝氯酸酪氯酸半膀氨酸 lp q r 亮氯酸 膈氯酸替氟酰胺精氧酸 a a it 异亮氯酸苏氯酸 ns 天冬酰胺丝氯酸 it kr 舁亮氯酸 苏氧酸籁贰酸精氯酸 m丁k r 甲硫氧酸 苏氨酸苏氯酸精氯酸 c a g 8 查垄堡燮堂堡主堂垡堡壅 一一 g vadgu 缬氧酸丙氯酸天冬氨酸甘氯酸 v 缬氯酸 a 丙氯酸 e 谷氯酸 g 甘氯酸 c a g 表1 1 中的三联体核曹酸是用r n a 碱基而非d n a 碱基表示，因为r n a 分子 提供了d n a 和蛋白质之间的关联另外，有三个密码子并不编码任何氨基酸而 是用于表示基因的终止，这三个特殊的终止密码在表中用s t o p 表示 下面我们介绍d n a 信息是如何指导蛋自质合成的一个识别基因或基因 簇起始的机制是启动于( p r o m o t e r ) 启动子是基因前面的一段d n a 序列，密码 子a u g 则是基困开始的信号识别出基因的起始点后，基因到r n a 的拷贝就 开始了，合成的r n a 称为信使r i v a ( m r n a ) ，其序列与d n a 的一条链相同， 但是u 代替了正该过程称为转录( t r a n s c r i p i o n ) 因r n a 是单链而d n a 是双链的，m r n a 在序列上与一条d n a 链相同 ( 只不过是矿代替了t ) ，与另一条链互补d n a 中，与m r n a 序列一致的链 称为反链( a u t i s e n s es t r a i a d ) 或编码链( c o d i n gs t r a n d ) ，而另一条链称为有意义链 ( s e m es t r a n d ) 、反密码链( a u t i c o d l n gs t r a n d ) 或模板链( t e m p l a t es t r a n d ) 实际上 被转录的是模板链，因为m r n a 是由与该链互补的核糖核酸组成的合成过程 是从5 端岛3 端，因此模板链是从3 端向擎端阅读的 上述的转录在原核生物( p r o k a r y o t e ) 中是正确的在这些生物中，由于缺乏 核膜，d n a 是自由悬浮于细胞中的但在真核生物( e u k a x y o t e ) 的细胞中有细胞 核，d n a 位于细胞核中，其转录模式更为复杂许多真核细胞基因具有不同的 组成部分，即内含子( i n t r o n ) 和外显子( e x o n ) 转录后内含子必须从m r n a 中切 除，这意睬着内含子不参与蛋白质的合成在内含子被剪切后，离开细胞核的剪 短的m r n a 仅含有外显子与起始和终止的调控序列 因为有内含子和外显子，我们用不同的名字命名染色体上的全基因和剪切 后仅含外显子的基囡前者称为基因组d n a ( g e n o m i cd n a ) ，后者称互补d n a ( c o m p l e m e n t a r yd n a ) 或e d n a 通过细胞核外的m r n a ，然后使用个称为反转 9 r 4 的二级结构 录( r e v e r s et r a n s c r i p t i o n ) 的过程，以m r n a 为模板合成c d n a 这样，人们可以 不经染色体面获得c d n a ，在某些生物体中也存在反转录现象，例如，反病毒通 过反转录的机制能将它们的r n a 基因组复制成d n a 现在让我们重新回到m r n a 和蛋自质合成在这个过程中另外两种r n a 分子起到重要的作用蛋白质的合成是在细胞内被称为核糖体中进行的核糖体 由蛋白质和被称为核糖体r n a ( r i b o s o m a lr n a ，r r n a ) 的大分子组成遗传信 息从r n a 传到蛋白质的过程称为翻译( t r a n s l a t i o n ) ， 实际上，遗传密码的翻译是由t r n a 实现的，它连接密码子和其所编码的 氨基酸当m r n a 穿过核糖体内部时，t , r n a 匹配当前的密码子，即当前位于 核糖体内部的m r n a 密码子，与它结合，并带进对应的氨基酸( 细胞中总是悬 浮着大量的氨基酸) 这些分子此时所处的空间位置使他们可以完成下列操作，即 随着t r n a 与密码子结合，新结合的氨基酸紧靠先前已形成的氨基酸链，一个合 适的酶则催化该氨基酸加入肽链，然后释放t r n a 蛋白质按这种一个氨基酸接 一个氨基酸的方式合成起来当出现终止密码子时，没有t r n a 与之对应，合成 便终止，m r n a 被释放，并被降解成核糖核苷酸 总结上面描述的过程，细胞内遗传信息的流动通常用中心法则( c e n t r a ld o g m a ) 来说明 反转录 图1 1 分子生物学的中心法则 f i g u r e 1 1c e n t r a ld o g m a 1 0 3 r n a 二级结构知识概论 r n a ( 即t r n a ，r r n a ，m r n a 和s n r n a ) 有两大主要功能t 一是某些病毒的 遗传物质；二是参与蛋白质的合成这些与细胞分化、代谢、记忆的储存等有重要 关系为了更好的了解r n a 的功能，解读遗传密码，就需要剖析r n a 的结构 对于r n a 的高级结构传统分析是生物化学和生物物理学方法这不仅费时，且只 能用于小分子r n a 的研究( 如t r n a ，只含有七八十个核昔酸) ，对大分子r n a ( 如 r r n a ，含几百几千个核苷酸) 就相当困难由于多数r n a 含碱基达1 0 3 以上，目 前依靠实验手段很难给出它们的二级结构借助计算机来预测i ：i n a 的高级结构是 一种很经济的手段近些年来，有关r n a 分子二级结构的研究一直很活跃，给 出了不少预测方法如m a x i m a lm a t c h i n g 方法 2 ，m i n i m a lf r e ee n e r g y 方法 2 3 ， d y n a m i cp r o g r a m m i n ga l g o r i t h m s 4 】以及t r e ea d j o i n i n gg r a m m ”s 5 等，并编写了程 序，预测了许多r n a 分子的二级结构，不过许多预测结果与实验结果常有出入， 结构不稳定 所谓r n a 二级结构的预测，就是计算给定长度的r n a 序列的最优结构目 前所有预测算法要预测出所有序列的二级结构仍然非常困难，自然估计给定长度的 所有可能的二级结构数则成了数学任务这些结果在负面意义上对生物学有用，它 肯定了存在巨大数量的特殊结构数，直接枚举是没有希望的，并且它间接地决定了 预测算法的时间复杂性和空间复杂性在本文中我们应用组合计数的技巧，考虑了 r n a 二级结构及子结构的计数问题 3 1 预备知识 3 1 1 r n a 二级结构预测方法的发展 v a n h e i j n e ( 1 9 8 7 ) 6 】对各种预测r n a 二级结构的方法进行了综述t i n o c oe to f ( 1 9 7 1 ) 7 首次估算了与= 级结构相关的能量，他通过对小分子进行研究，再运用外 r n a 的二级结构 推法来预测大分子能量最稳定的结构能量估算包括双链区中堆叠碱基对相关的 稳态能量和未配对区域的不稳定影响，p i p a s 和m c m a h o n ( 1 9 7 5 ) 8 】8 开发的计算机 程序可以列出t r n a 序列中所有可能的螺旋区他们采用改进的w a t s o r * 一c r i c k 碱基配对原则，通过排列组合合适的螺旋来获得所有可能的二级结构，并评估了 每个可能结构的总自由能s t u d n i c k 等( 1 9 7 8 ) 9 设计了一种方法将适合的双链 区相加获得能量最适结构m a r t i n e z ( 1 9 8 4 ) 1 0 1 列出了可能的双链区，然后通过 计算玻兹曼函数e z p ( a g r t ) 给出这些区域在其平衡常量中的比例，这里的 一a g 为这些区域的自由能，矗是气体常数，t 代表温度用m o n t ec a r l o 方法 折叠r n a 分子，在该方法中每一个起始区都是由一个加权集合中随机选择的， 这与用于吉不斯取样的方法是相似的 假设每个可能的双链区可以用包中的弹子来表示每种类型的弹子用玻兹 曼概率赋以权重，这样能量越稳定的区域相对应的弹子就越有可能被选中其 他可能区域可以通过权重进一步选择，直到没有可加的为止这一方法产生了一 系列依能量加权的可能结构，但没有考虑未配对区域的不稳定影响玻兹曼概率 函数近来已被用于寻找最可能的二级结构( h o f a c k e r 等，1 9 9 s 1 1 ；w u c h t y 等， 1 9 9 9 1 1 2 ) n u s s i n o v 和j a c o b s o n ( 1 9 8 0 ) 1 3 首次设计出一个用于预测二级结构的精确而 有效的算法该算法产生了2 个计分矩阵：一个是m ( i ，j ) ，表示由i 和j 之间任 意间隔形成的碱基对的最大数目；另一种是k ( i ，) ，表示和j 碱基相配对的碱基 位置女这两个表中具有最大可能碱基对数目的结构是由一个回溯过程推导出来 的；该过程类似于用动态规划进行序列对位排列z u k e r 和s t i e g l e r ( 1 9 8 1 ) 用 动态规划算法和能量规则来获得能量最适结构该方法假设在分子中能量最高的 ( 通常也是最长的) 就是预涮的d s r n a 区因为许多双链区对大部分的i ：i n a 是 可预测的，而预测数目的缩减是通过考虑已知的生化和结构信息以指出哪些碱基 应该配对或不配对，通过强制拓扑约束以及通过结构应处于一个能量稳定的结构 中这一需求来实现的 m i c h a e lz a k e r 及其同事编写的m f o l d 通常甩于预测一个r n a 分子的能 量最稳定结构( j a e g e r 等，1 9 8 9 ，1 9 9 0 ；z u k e r ，1 9 8 9 ，1 9 9 4 ) m f o l d 可提供在给定能 量范围内一系列可能的结构及其可靠性该程序还采用了系统发育相关序列的协 同变异信息( z u k e r 等，1 9 9 1 1 1 4 ) m f o l d 中包括所预测序列的图形显示方法 该程序是目前的最需要计算机资源的，因为其算法复杂性为a ，这里n 为序列 长度若序列长度加倍，则计算结构的时间增加8 倍这一程序也需要大量存贮 空间，来保存多重记分矩阵中序列能量的中问计算m f o l d 多用于预测小于 1 2 大连理工大学硬士学位论文 1 0 0 0 个核苷酸长度的序列的结构该方法对一些小分子非常可靠，但随着序列长 度的增加，其可靠性随之下降 m f o l d 和其他许多关于r n a 的有用信息可以在m i c h a e lz u k e r 的网站 t 扣：b i o ：o m a t h r 硝d e u z u k e r r n a 中获得这里没有给出运行m f o l d 的细节，因为可以阅读其用户手册( j a e g e r 等，1 9 9 0 1 1 5 ) 最近，维也纳l c l n a 研 究组报刭了种称为分配函数的新方法，可用于寻找r n a 分子最可能的二级结 构及最可能的碱基对( w u c h t y 等，1 9 9 9 1 1 2 ) r n a 结构预测方面的一个进展来自于识别某些r n a 序列形成特定结构以 及这些序列的存在是否可以预测这样的结构例如，c u u c g g 在不同的遗传背 景中出现，并且形成个非常稳定的结构( t u e r k 等，1 9 s 8 1 1 6 ) 包含这种r n a 结构和序列的数据库就可以帮助我们进行r n a 结构预测 遗传算法也已用于预测二级结构( s h a p i r o 和n a v e t t a ，1 9 9 4 17 ) 为了排列 r n a 序列，需要考虑序列和二级结构( 包括假结) ( n o t r e d a m e e ta l ，1 9 9 7 1 1 8 1 ) 在计 算r n a 折叠路径的时候也需要作同样考虑( g u l t y a e 等，1 9 9 5 1 1 9 1 ) f l o d a l i g n 程序采用一种动态规划算法，基于序列和二级结构的对r n a 进行排列，并找到 最显著的基序( g o r o d k i n 等，1 9 9 7 1 2 0 ) c h a n 等( 1 9 9 1 ) 2 1 】介绍了另一种相同目 的的算法c h e t o u a n i 等( 1 9 9 7 ) 2 2 则开发了e s s a 方法，用于显示和分析r n a 二级结构 3 1 2 r n a 二级结构预测基本原理 p l a t a 二级结构是通过分子中的碱基之间配对形成的碱基之间配对有三种 类型tg 。c 、a - u 和g u ，它们之间分别有三个、- - + 和一个氢键碱基之间的 连续配对形成靖l 旋区，对r n a 二级结构起著稳定作用，从而降低整体结构自由 能，而r n a 分子中没有配对的部分形成环状结构( 发卡环、内部环、膨涨圈和 多分支环) ，不利于结构的稳定，升高结构自由能，r n a 二级结构的形成就是在 这种矛盾之间的一种平衡预测r n a 二级结构最常用的方法就是在各种可能结 构之间寻找最小自由能结构，而基本结构的自由能数据是通过研究体外寡核苷酸 稳定性获得的最常用的自由能数据为s a l z e r 和t u r n e r 能量积分系统2 3 1 ，但在 这两组数据中，没有提及多分支环的能量计算，目前般将之作内部处理，或用 公式计算：4 7 + 0 4 x 单链碱基数+ o 1 螺旋区数目有了这些数据，就可评价 r n a 二级结梅的稳定性，通过这种方法可以得到近乎稳定能量的结构和最可靠 的预测结构在相关序列中发现的序列变异也可用于预测哪种碱基配对有可能在 1 3 r n a 的二级结构 每个分子中都存在r n a 结构预测方法的一种变体是预测一组可能形成一种特 定结构的序列从序列预测三维结构的方法正在发展之中另一种常见r n a 二 级结构预测方法考虑了碱基配对的保守模式，这些模式在一类给定的r n a 分子 进化过程中是保守的发现序列中碱基配对的区域在r n a 分子进化的同时发生 变化，使得结构的完整性得以维持饲如，如果在一个给定类型的序列中两个位 置( g 和g ) 形成一个碱基对，则在相应的位置上保留了g 和c 、a 和u 或u 和 a 的序列被认为是可能的匹配，r n a 分子中这些协同变异模式是置a 二级结 构的一种表现，可依此预测结构计算上遇到的挑战是如何在其他序列变化的背 景中发现这些协同变量的位置 3 1 3r n a 二级结构表示 r n a 二级结构表示方法很多，如半圆表示、圆形表示、点阵表示、山峰表 示、正多边形表示等，其中以正多边形表示最为直观形象，便于分子生物学家观 察，研究r n a 二级结构特征，但是利用这种方式来比较不同的结构是较为困难 的，因为利用这种表示方式时，常导致许多子结构的重叠，为此，人们不得不借 助于旋转的办法来克服重叠现象，这样一来，即使是对同一种结构，可能由于在 不同的地方旋转或在同一地方旋转的角度不同而导致结构形状的变化目前，再 现结构或对结构进行比较的最好方法是树状表示方法，这种方法是从图论的角 度来考虑的，与上述方法不同，在r n a 二级结构中。每个配对碱基用一个点表 示，然后用一条有向线段将点按顺序连接起来，便可获得r n a 二级结构的树状 表示，在这种显示中，环区碱基等信息将被丢失 3 1 4 r n a 二级结构的特征 如同蛋白质的二级结构一样，r n a 二级结构也可以简单地认为是形成三维 结构的一个中f 曰步骤r n a 二级结构由双链r n a 区域组成，这些双链r n a 区 域是通过单链分子内自身折叠形成的为了产生这样的双链区 r n a 序列下游区 域一连串碱基必须和另一个上游区域互补，使得互补的核苷酸g c 和a u ( 如同 d n a 中的c c 和a t 碱基对一样) 产生w a t s o n c r i c k 碱基此外，在这些双 链区中可能产生g c 的不稳定配对如同在d n a 中样，c c 碱基对使分子的 能量稳定性最高，a u 碱基对的能量稳定性较低，人们已经根据已解析的r n a 结构，识别出这些碱基对和其他一些碱基对( b u r k h a r d 等，1 9 9 9 a , b 2 4 ) r n a 结 构预测中包含了不同的环和接头中配对与不配对的区域，如下图所示t 1 4 大连理工大学硕士学位论文 5 5 3 ，r 弋 i 5 3 a 单链r n a c 茎和环或发夹环 e 内环 1 5 3 5 3 ；卫卫 b 堆叠碱基对的双链嘲旋 3 5 3 d 凸环 3 5 5 3 f 接头或多重环 3 r n a 的二级结构 除了r n a 中二级结构的相互作用外，还有第三种相互作用，如下图所示这些 结构不能用二级结构预测程序来预测它们只能通过协方差分析来发现 a 假结 b 相吻发夹 c 发夹一凸环连接 3 1 5 r n a 二级结构预测的局限性 在预测r a 二级结构时，常常需要一些简化假设首先，最可能的结构类似 于能量最稳定的结构其次，结构中与位置相关的能量仅仅受局部序列和结构的 影响r 因此，与双链区中一个特定碱基对相关的能量可以认为只受蓟其前面碱基 对的影响，而与双链中较远碱基对或结构中其他碱基对无关此能量可以通过小 1 6 大连理工大学硕士学位论文 的合成r n a 寡核苷酸的实验来进行可靠估计( t i n o c o 等，1 9 7 1 ，1 9 7 3 1 2 5 ；f r e i e r 等，1 9 8 6 1 2 6 ；t u r n e r 和s u g i m o t o ，1 9 8 8 1 2 7 ；s a n t a l u c i a ，1 9 9 8 1 2 8 ；m a t h e w s 等， 1 9 9 9 1 2 9 ) 当用于标准w a t s o n c r i c k 碱基对以及w a t s o n c r i c k 碱基对环绕的 单一g - u 对时，它们是最可靠的最后，假设此结构是由链自我折叠形成的， 在折叠过程中遵循不产生任何结的规则表示这一要求的最佳方式是将序列画成 环状图，然后用弧线连接配对碱基如果具有所有预测碱基对的总体结构都不打 结，则所有弧线均不交叉( 如图3 1 ) 可是，若在图中出现个假结( 如上页的图) 线条将出现交叉 a b 图3 1 用环状图表示r n a 二级结构中的碱基配对b 中示出预测的最小自由能结构 图中预测的配对碱基以弧线的形式与序列中其他碱基相连，在图a 中显示为环 绕球体的弧线没有线条交叉，即表示此结构中没有结 3 2 典型r n a 二级结构预测算法 鉴于r n a 二级结构的复杂性，人们在解决问题时总是从各种不同的角度尽 可能尝试各种可行的手段去考察它，希望能找到更好的办法，因此也就产生了各 1 7 r n a 的二级结构 种各样的方法，可以说是五花八门层出不穷总的一个趋势就是相互之间取长补 短，尽可能把各种有用的信息都利用上，在尽量减小计算复杂度的情况下，使自 己的计算结果更加接近于真实情况从算法立意的角度看，我们可以把