（计算机科学与技术专业论文）基于堆积协变信息的rna二级结构预测算法研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 r n a 二级结构预测在生物信息学研究中具有重要意义。含伪结的r n a 二级 结构预测是r n a 研究中的热点和难点问题。研究人员已经从各个角度提出了多 种预测方法。现有含伪结r n a 二级结构预测算法的主要问题在于算法预测精度 比较低、时间复杂度过高两个方面。本文针对这两个问题，分别从改进堆积协变 信息模型和使用计算较简单的能量模型两个方面，对同源r n a 序列的含伪结公 共二级结构预测算法进行研究。本文提出的算法提高了含伪结r n a 二级结构的 预测精度，具有较低的时间复杂度。本文主要包括以下两部分的内容和结果： 一、提出了一种基于改进后的堆积协变信息模型和最小自由能模型预测同源 r n a 家族序列含伪结二级结构的算法。该算法在c s f o l d 算法基础上，区分相邻 碱基配对对参考碱基配对的正面影响和负面影响，提出通过阂值控制协变信息得 分计算，改进堆积协变信息模型。并结合最小自由能预测含伪结的r n a 二级结 构。数值实验表明，该算法能正确预测伪结，其平均敏感性和特异性优于现有算 法。 二、提出了一种基于堆积能量和堆积协变信息的r n a 二级结构预测迭代算 法。该算法在s m h 算法基础上，使用较简单的堆积能量模型，并引入改进后的 堆积协变信息模型，通过迭代得到同源r n a 家族含伪结的公共二级结构。该算 法具有较低的时间复杂度o ( n 3 ) 。数值实验表明算法具有较高的预测敏感度和特 异性，并且可以预测伪结。 主题词：r n a 二级结构预测，堆积协变信息，堆积能量，伪结，迭代算法 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t t h ep r e d i c t i o no fr n as e c o n d a r ys t r u c t u r eh a si m p o r t a n ts i g n i f i c a n c ei n b i o i n f o r m a i t c s i ti sah o t s p o ta n dd i f f i c u l t yi nr n a r e s e a r c h m a n ym e t h o d sh a v e b e e np r e s e n t e df r o md i f f e r e n tv i e w p o i n t s t h ep r e s e n tm e t h o d sc a n n tp r e d i c t s s t r u c t u r e si n c l u d i n gp s e u d o k n o t sw e l l t h es h o r t c o m i n g t so ft h ep r e s e n tm e t h o d s i n c l u d e st w oa s p e c t s t h eo n ei sl o wa c c u r a c y a n dt h eo t h e ri sr e l a t i v e l yh i g h c o m p l e x i t y o nt h i si s s u e ，t h i st h e s i ss t u d i e sa ni m p r o v e dc o v a r i a n c em o d e lt o i m p r o v et h ea c c u r a c y ，a n du s i n gas i m p l e re n e r g ym o d e lt or e d u c et h ec o m p l e x i t y t h et h e s i sm a i n l yi n c l u d e st w os e c t i o n so fc o n t e n t sa n dc o n c l u s i o n sa sf o l l o w i n g ( 1 ) b a s e do ni m p r o v e ds t a c k i n gc o v a r i a n c em o d e la n dm i n i m u m f r e ee n e r g y ，t h e t h e s i sp r e s e n t sa na l g o r i t h mt op r e d i c tt h ec o n s e n s u ss t r u c t u r ei n c l u d i n gp s e u d o k n o t s o fh o m o l o g yr n as e q u e n c e s o nt h eg r o u n do fc s f o l d ，t h et h e s i sd i s t i n g u i s h st h e a d v a n t a g e da n dt h ed i s a d v a n t a g e do ns t c a k i n gc o v a r i a n c e ，a n du s e sat h r e s h o l dt o c o n t r o lt h ec a l c u l a t i o no ft h es t a c k i n gc o v a r i a n c e t h e nt h et h e s i sc o m b i n e st h em o d e l o fi m p r o v e ds t a c k i n gc o v a r i a n c e 、) l ，i t l lm i n i m u mf r e ee n e r g yt 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 s 、j l ，i 廿lp s e u d o k n o t s t h en u m e r i c a lt e s t ss h o wt h a tt h i sa l g o r i t h m c a nc o r r e c t l yp r e d i c tp s e u d o k n o t s ，谢t ht h em e a ns e n s i t i v i t ya n ds p e c i f i c i t yb e t t e rt h a n t h a to fo t h e ra l g o r i t h m s ( 2 ) b a s e do ni m p r o v e ds t a c k i n gc o v a r i a n c em o d e la n ds t a c k i n ge n e r g ym o d e l ， w ep r e d i c tr n as e c o n d a r ys t r u c t u r e s 、 ，i t l lp s e u d o k n o t so nt h eg r o u n do ft h es m h a l g o r i t h m t h er n as e c o n d a r ys t r u c t u r ei sc o m p o s e db ys t e m s w ec o m p u t et h es e t o fs t e mb yi t e r a t i v ea l g o r i t h m w h e nt h ei t e r a t i o nb e g i n s ，w ew i l lg e tas t e mw h i c h h a st h em a x i m u ms c o r ee v r yt i m e t h es c o r ei sc o m p o s e db yt h es t a c k i n ge n e r g yo f t h es t e ma n dt h ev a l u eo fs t a c k i n gc o v a r i a n c e t h et i m ec o m p l e x i t yo ft h ea l g o r i t h m i so ( n 3 ) t h en u m e r i c a lt e s t ss h o wt h a tt h em e a ns e n s i t i v i t ya n ds p e c i f i c i t yo ft h e a l g o r i t h ma r ee q u i v a l e n t 晰t ht h er e f e r e n c ea l g o r i t h m s ，a n dt h a tt h et i m ec o m p l e x i t y i sl o w e rt h a nt h a to fo t h e ra l g o r i t h m s k e yw o r d s ：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 ，s t a c k i n gc o v a r i a n c e ， s t a c k i n ge n e m y ，p s e u d o k n o t s ，i t e r a t e da l g o r i t h m 第i i 页 国防科学技术大学研究生院硕士学位论文 表 目录 表3 1 实验测试序列2 3 表3 2 使用c l u s t a l w 比对序列比较协变信息改进前与改进后的性能2 6 表3 3使用c l u s t a l w 比对序列比较c e f o l d 与p k n o t s 、i l m 的性能2 7 表4 13 7 时相邻碱基之间的堆积自由能2 9 表4 2 使用c l u s t a l w 比对序列比较m s c f 与p k n o t s 、i l m 、c s f o l d 的性能3 5 表4 3使用结构比对序列比较m s c f 与i l m 、c s f o l d 的性能3 6 表4 4m s c f 与c s f o l d 时间消耗比较3 7 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1从r n a 一级结构到鼬叮a 三级结构2 图2 1r n a 二级结构子结构类型7 图2 2 e s c h e r i c h i ae o l im i 冱6 0 0 的二级结构8 图2 3 嵌套配对结构9 图2 4 非嵌套配对模式( 伪结) 9 图2 5 m f o l d 算法中w ( i d ) 和v ( i j ) 的表示1 1 图2 6p k n o t s r g 中伪结计算模型图1 2 图2 7 两个非伪结结构形成一个伪结1 4 图3 1h d v 家族参考序列a j 3 0 9 8 8 0 真实结构图2 4 图3 2改进前h d v 家族参考序列a j 3 0 9 8 8 0 预测结构图2 5 图3 3改进后h d v 家族参考序列a j 3 0 9 8 8 0 预测结构图2 5 图4 2e n t e r r o v i r u s 家族参考序列m 8 8 4 8 3 真实结构图。3 2 图4 3e n t e r r o v i r u s 家族参考序列m 8 8 4 8 3 预测结构图。3 3 图4 4s r pr n a 家族序列h a l h a l 真实结构图3 4 图4 5 s r pr n a 家族序列h a l h a l 预测结构图3 4 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基王丝抠协变焦! 垦鲍丛三熟箜抱亟到箕洼研究 学位论文作者签名：蕴l 煮j 幺日期：7 ，7 年z 月z 7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题艮基王丝塑迹变焦皇鲍堡丛三熟结捡亟测篡洼珏究 学位论文作者签名：杰! 扭危 日期：劲，7 年二月坪日 作者指导教师签名： 和( n a t u r e ) 连续四年将r n a 的研究列为重 大科学成就。继d n a 和蛋白质之后，r n a 正在成为生命科学新的研究热点。 过去人们认为，r n a 只是d n a 和蛋白质之间的信息传递者。二十世纪八十 年代初，c e s h 等人发现r n a 也是一种生物催化剂，并称之为核酶。由此，人们 开始意识到r n a 的角色并非只是“遗传信息的传递者 ，它还有更多的功能。 研究逐步表明，r n a 通过各种类型的剪接，编辑和再编码来控制遗传信息的表 达，并且通过调控和催化蛋白质的生物合成来控制生命中枢。近几年来，随着越 来越多r n a 基因及其功能被识别和揭示，人们逐渐认识到r n a 和蛋白质分子 一样重要甚至是主要的功能性分子l i l 。 r n a 的功能是由其结构所决定的。如t r n a 的转运功能，s n r n a 剪切功能， c a m p 的信使功能等都需要r n a 特定的结构才能完成【2 】【3 】。在r n a 分子各种子 结构中，伪结普遍存在并且也有着重要的生物功能。研究表明，一些病毒核糖体 上的伪结结构和某些疾病有着密切的关系。因此，研究r n a 结构，特别是伪结 结构，对于理解r n a 功能、认识r n a 结构和功能之间的关系有着重要的意义。 r n a 由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 结构和功能之间的关系，关键问题就是获取r n a 三级结构。但是r n a 分子具有降解快、x 射线衍射法所需的r n a 晶体难以获得等特点，用物理实验 方法获得r n a 三级结构成本高昂且非常耗时。因此，直接研究r n a 三级结构 十分困难。r n a 三级结构是由其一级结构，即r n a 序列所有碱基的排列顺序决 定的【4 j 【5 j ，不同的碱基顺序对应着不同的r n a 分子并决定了其相应的结构与功 能。而目前基因组测序技术已经比较完善，获得r n a 的序列信息已经不是问题。 所以由一级结构推测得到三级结构成为r n a 结构预测的研究热点。 第1 页 国防科学技术大学研究生院硕上学位论文 由r n a 的一级结构直接推测得到三级结构是非常困难的，现在的解决办法 圈l1 从r n a 一级结构到r n a 三级结构 r n a 二级结构有着非常重要的研究价值，它是由r n a 一级结构推测三级结 构的桥梁和纽带。而且它可以应用于诸如t r n a 和蛋白质的相互作用、m r n a 的 稳定化处理以及将r n a 注入到病毒微粒里等方面p j 。 随着基因组测序的完成，产生了海量的r n a 序列数据，通过实验方法确定 r n a 结构已经无法对这些海量的数据进行及时的处理，进而严重制约了r n a 的 研究和发展。因此，借助计算机手段预测r n a 结构，是我们认识r n a 结构的 一个有效途径。 l _ 2 研究现状 目前，r n a 一- - 级结构的经典预测方法主要有两类：基于热力学自由能的方 法卧、基于比较序列分析方法【1 丁儿1 ”。由于针对伪结进行建模非常困难，一旦 引入伪结，将大大增加结构预测算法的时间复杂度，所以早期的结构预测研究都 不预测伪结。但伪结在r n a 分子中普遍存在，井对r n a 的功能起着重要的块定 第2 页 国防科学技术大学研究生院硕士学位论文 作用。所以近年来研究者开始关注伪结的研究。下面简要讨论当前r n a _ - - 级结 构预测的几种方法。 一、基于热力学最小自由能方法。在熟力学上，稳定的r n a _ - - 级结构应该 是具有最小自由能量的结构。该方法以单条r n a 序列为输入，预测具有最小自 由能的二级结构。在r n a - 级结构中，碱基配对是降低i 玳a 二级结构能量最主 要的因素。因此，最早i 由n a s s i n o v 8 】使用动态规划算法，求得具有最大碱基配对 数的二级结构。其后z u k e r 9 卜0 1 1 等人在此基础上，考虑碱基配对之间的作用以及 环的能量，将二级结构划分为多种模体( m o t i f ) ，每种模体根据环长度具有不同的 能量，使用动态规划算法求得具有最小自由能的二级结构。在某种程度上，使用 最小自由能方法预测r n a 二级结构可以说是从z u k e r 等人开始的。z u k e r 算法【1 0 】 的时间复杂度为伙n 4 ) ，空间复杂度为0 ( n 2 ) 。该方法不能预测伪结。r i v a s 和e d d y 基于最小自由能提出了能够预测伪结的动态规划算法p k n o t s 1 2 1 1 1 3 】，该算法可处 理的伪结类型十分丰富。但其时间复杂度为饿n 6 ) ，空间复杂度y g o ( n 5 ) 。b l y n g s q b 等人【1 4 】以及李恒武和朱大铭【1 5 】对p k n o t s 算法进行改进，通过限制环长度和预测伪 结的类型将时间复杂度降低到o ( n 5 ) 。由于基于最小自由能的动态规划算法高昂 的时空消耗，限制了该算法的应用，其只能处理短序列r n a 。该类算法还包括 能处理简单伪结的p k n o t s r g 1 6 】等。 最小自由能方法的预测精度主要受能量参数的影响。使用动态规划算法预测 含伪结的r n a - - 级结构，只有在预测短序列r n a 时，才会获得具有较高准确率 的结果。由于时空复杂度较高以及对伪结的能量参数认识不够深入等问题，该方 法在预测长序列r n a 含伪结的二级结构时准确率较低。该方法主要的缺陷在于 时间复杂度较高，为伙1 1 4 卜o ( n 6 ) 。 二、基于比较序列分析方法。该方法以多条同源r n a 家族序列作为输入， 预测同源序列的公共保守二级结构。在分子生物学中，r n a 结构保守性大于序 列保守性，这就意味着在生物进化过程中，即使r n a 序列的个别碱基发生变化， r n a - - 级结构也很可能保持不变。因此，当配对的某个碱基变异时，为了保持 原有的配对，另个碱基也随之改变，这就是协变现象。 基于比较序列分析方法通过度量同源序列间的协变关系来来预测他们公共 的二级结构。这种方法的预测精度对输入同源序列比对质量的依赖度较高，比对 质量越高，预测的精度也就越高。典型的基于比较序列分析方法的算法有 r n a a l i f o l d t l 7 j 和p f o l d t l 8 j 等。 r n a a l i f o l d 1 7 】从r n a l g 对中计算出一致结构。它是z u k e r 算法f i o 】的一个扩展， 时间复杂度为伙n 3 ) ，空间复杂度为伙n 2 ) 。r n a a l i f o l d 只能预测长度小于3 0 0 个核 苷酸的序列。 第3 页 国防科学技术大学研究生院硕士学位论文 p f o l d 1 8 】使用上下文无关文法，结合了r n a 的进化信息来预测i 矾a 的二级结 构，该算法时间复杂度比较低，预测精度也比较高。当序列较长，同源r n a 家 族序列个数较多时，很适合使用该算法进行预测。但该算法的缺点是不能预测含 伪结的r n a - - 级结构。 比较序列分析方法通过多条同源序列之间的协变关系预测r n a 保守二级结 构，其预测结果正确率相对最小自由能方法要高。但缺点是对输入同源序列的比 对质量依赖程度较大。而当前多序列比对仍是生物信息学研究的一个难点问题。 同时，对于含伪结的尉峪二级结构预测，该方法时间复杂度较高。 还有一些方法结合以上两种方法，采用启发式算法预测砌蛆二级结构，并 且具有较好的性能。这些算法包括迭代算法【1 9 卜【2 1 1 、遗传算法【2 2 】【2 3 1 和神经网络算 法【2 4 1 1 2 5 1 等。其代表性的程序有i l m 2 0 、s t a r 2 2 1 、k n e t f o l d l 2 4 1 等。启发式算法有 着高效性、并行性和灵活性的优点，能够预测伪结，预测准确性也比较高。该类 算法的时间复杂度在d ( n 3 卜d ( n 4 ) 之间。启发式算法共同的缺点是：它们都是一种 随意性很大的黑箱方法，无法保证收敛到或着靠近全局最优解，也无法判断给出 预测结果哪个更好或者哪个结果离最优结构最接近。 当前r n a - - 级结构预测算法的主要问题是时间开销很大。不含伪结点的 r n a _ - - 级结构预测算法，时间复杂度为d ( n z 卜伙一) ；含伪结的r n a - - 级结构预 测算法时间复杂度相对要高很多，大都在0 ( n 4 ) 与伙n 5 ) 之间。 综上所述，含伪结的r n a 二级结构预测是目前r n a 研究中的热点、难点 问题，解决该类问题普遍存在时间复杂度和空间复杂度过高的问题，而且算法的 预测准确率也有待于进一步提高。 1 3 论文的主要研究内容 本文主要研究基于堆积协变信息的r n a 二级结构预测算法。在深入研究结 构预测理论、剖析现有典型算法的基础上，一方面改进堆积协变信息模型，并结 合热力学最小自由能方法预测含伪结的r n a 二级结构；另一方面结合堆积能量 和改进后的堆积协变信息模型，设计时间复杂度较低的含伪结r n a 二级结构预 测算法。 本文的主要工作如下： 一、深入研究和分析当前r n a 二级结构预测的现状和优缺点。 二、提出通过阈值b 控制堆积协变信息得分的计算，改进堆积协变信息模 型。在c s f o l d 算法【1 9 】基础上，结合堆积协变信息模型和最小自由能模型，实现 一种含伪结的r n a 二级结构预测算法c e f o l d 。 三、在s m h 算法【2 6 】基础上，引入堆积协变信息模型，提出了一种基于堆积 第4 页 国防科学技术大学研究生院硕士学位论文 能量和协变信息的含伪结r n a 二级结构预测算法m s c f 。m s c f 算法使用计算 较简单的堆积能量模型，降低了二级结构预测算法的时间复杂度。算法采用迭代 思想逐步形成r n a 二级结构，能够预测伪结。 本文的主要创新点在于： 一、区分相邻碱基配对对参考碱基配对的正面影响和负面影响，改进堆积协 变信息模型，一定程度上提高了算法的预测精度： 二、提出通过阈值b 木控制堆积协变信息计算； 三、提出基于堆积能量和堆积协变信息计算模型，在很大程度上降低了预测 算法的时间复杂度； 本文结构如下： 第一章，主要讨论了r n a 二级结构的研究意义和研究现状。 第二章，主要讨论并分析与本文工作相关的一些典型的r n a 二级结构预测 方法。 第三章，针对当前算法预测准确率较低的问题，改进堆积协变信息模型。结 合最小自由能模型，预测含伪结的r n a 二级结构。然后通过数值试验，分析该 方法的预测准确率和复杂度。 第四章，针对当前预测算法时间复杂度较高的问题，使用计算较简单的堆积 能量模型，结合改进后的堆积协变信息计算模型，使用迭代算法预测含伪结的 r n a 二级结构。最后通过数值实验，分析了该算法的预测准确率，并分析了算 法的时间复杂度。 第五章，对全文工作进行总结，并对以后的研究工作进行展望。 第5 页 国防科学技术大学研究生院硕士学位论文 第二章r n a 二级结构的预测算法基础 迄今为止，r n a 结构预测已经产生了很多方法。为了得到更加接近真实结 构的预测结果，研究人员从不同角度采用各种可行的方法去研究与分析。经过三 十多年的发展，研究者在r n a 结构预测已经取得了丰硕的成果。r n a 二级结构 预测算法大致分为基于最小自由能方法和基于比较序列分析方法两种，还有一些 结合两种方法的启发式方法。 本章首先介绍r n a 二级结构的一些基本概念，然后重点讨论并分析和本文 工作相关的一些r n a 二级结构预测经典算法。 2 1 基本概念 定义2 1r n a 序列r n a 序列可表示成长度为n 的序列s ： s = $ 1 5 2 s ， j 。，f = 1 , 2 n 其中= a ，c ，g ，u 。 定义2 2碱基配对：r n a 的四种碱基通过氢键形成w a s t o n c r i c k 配对 a = u 、c r 兰- - c 和w o b b l e 配对g u ，通称为碱基配对并记碱基配对集p 为： p = a u u ac g ，g c ，g - u ，u g ) 。 定义2 3 堆积：两个相邻的碱基配对构成堆积，即碱基配对i j 和碱基配 对i + l j - 1 构成堆积。 r n a 和d n a 不同，是单链结构。r n a 序列通过自身形成二级结构。设碱 基s i 和s j 形成碱基配对i j ，其中i 勺。一般情况下，r n a 二级结构应满足以下 条件： ( 1 ) 任意碱基如果和其他碱基形成配对，则只能与另外唯一一个碱基形成 配对。 ( 2 ) 碱基配对之间不能交叉。即如果i _ ， 七 3 。 以上三个条件中，条件( 1 ) 限制一个碱基只能与另外一个碱基配对。条件 ( 2 ) 限制了碱基配对之间不能出现交叉，即结构中不能包含伪结。如果s 不满 第6 页 国防科学技术大学研究生院硕士学位论文 足条件( 2 ) ，s 中就包含伪结。条件( 3 ) 规定了在r n a 二级结构中能形成的 最小发夹环长度为3 。 ，_ _ i 、 ， 、 内部配对 i 二二二g 田u u = _ 一 - - ) 闭环配对 t a 5 l 一 3 i 一 + u 闭i ：配对 ，一 3 i 一 茎环 b ，发夹环 内部配对 闭环配对 闭环配对 d ，内环 一一、 一， 、t 5 一 ， 一、，3 一 闭环配对 c 多分支环 、 i l 、 ， 、 ， 、一， e ，凸起环f 外部碱基 图2 1r n a 二级结构子结构类型 z u k e r 等【l o 】把r n a 二级结构分解为六种模体：茎环、发夹环、多分支环、 内环、凸起环和外部碱基。图2 1 9 j 中分别为六种模体。 如图2 1 a 所示，茎环又称为茎区或螺旋区，由两个或两个以上连续的碱基 配对组成的结构，也可说是由连续的堆积构成的结构。图中的茎环是由三个碱基 配对g c 、u g 、u a 组成的。 如图2 1 b 所示，发夹环是由一个碱基配对和被碱基配对封闭的自由基所组 成的结构。其中自由基的个数为发夹环的长度，一般情况下发卡环的长度大于3 。 图中的发夹环是由碱基配对g c 和被碱基配对封闭的三个自由基a 、c 、u 所 组成的。 如图2 1 c 所示，多分支环是由至少3 个碱基配对、凸起、内环和一个端环 所组成的结构。图中的多分支环是由三个碱基配对a u 、c g 、g c 和两个 碱基a 、a 构成的。 如图2 1 d 所示，内环是由两个不相邻的碱基配对和碱基配对之间包含的每 边至少一个自由基所组成的结构。内环的长度为碱基配对之间自由基的个数。图 第7 页 、， ，-t c 一 一 ， 一 ， 、-t e ，i 、 一 、i， 一 、 t t 一 一 ， 一 、一j 国防科学技术大学研究生院硕士学位论文 中的内环是由两个碱基配对g c 、a u 和两个自由基g 、g 组成，长度为2 。 如图2 1 e 所示，凸起环是由两个有一端相邻的碱基配对和碱基配对之间另 一端不少于一个的自由基所组成的结构。图中的凸起环由碱基配对g c 、a u 和自由基c 、a 、a 组成的。 如图2 1 f 所示，外部碱基是靠近序列端点不构成环结构的自由基。图中序列 端点处的四个自由基u 、a 、c 、a 即为外部碱基。 e s c h e r i c h i ac o l lm r e 6 0 0 1 c c gu aou g c c u g g c g gg c g c 2 g g u g g u c c c a cc 3 u g a c c c c u 生 o v 飘叫i 婚c 善掣吒a a 制& 0 们u c a a g 4a u - g a a g 刈g g c g a 5a c g u u c u 图2 2 e s c h e r i c h i ac o i lm r e 6 0 0 的二级结构 图2 2 是e s c h e r i c h i ac o l im r e 6 0 0 的二级结构，我们把此二级结构分解成上 面所说的若干个模体。图中1 、2 、3 、4 、5 所标识的连续的碱基配对为五个茎区。 茎区l 最左端碱基u 为外部碱基；茎区2 和茎区3 分别包含了长度为1 和2 的 凸起环；茎区3 的右端和茎区5 的下端分别是长度为1 3 和3 的发夹环，环内部 被包含部分碱基是自由基；茎区4 和茎区5 中间是一个长度为8 的内环：茎区2 、 3 、4 和茎区5 一起组成了一个多分支环。 第8 页 国防科学技术大学研究生院硕士学位论文 一u g c c g ca c c a u c a g c u a c g a a 际三虱 善。：岂 彳丫 ；l | | c c g c g a a c 丫f j 宁a ca a 山c g a a 暑u ci l 些型l鲥( ；： 图2 4 非嵌套配对模式( 伪结) 如果r n a 二级结构中含有伪结结构，那么我们称此结构为含伪结的r n a 二级结构。实验证明，伪结在r n a 中普遍存在，且伪结的类型和r n a 的功能 又密切关系。伪结一般分为平面伪结和非平面伪结两种。平面伪结是指碱基配对 的连接线能在平面图上表示出来而不出现交叉：非平面伪结则是不能在平面图上 表示出来而不使碱基配对的连接线不出现交叉。现在的算法一般只能预测平面伪 结，也有少数算法能够预测非平面伪结如p k n o t s 算法【1 2 】等。 2 2r n a 二级结构预测算法分析 本节讨论并分析和本文工作相关的几种典型r n a 二级结构预测算法。r n a 二级结构预测算法包括基于热力学最小自由能方法【8 卜【1 5 1 1 2 8 】【2 9 1 、比较序列分析方 法【1 7 】f 3 0 】【3 l 】 4 2 卜【4 5 1 和一些启发式算法1 1 8 j 【2 1 1 等。其中最小自由能方法预测单条r n a 序列的二级结构，比较序列分析法预测多条同源r n a 家族序列的公共二级结构， 启发式算法可以说是两者的结合。这些算法各有各的优点，也各有各的应用范围， 下面将详细讨论这些算法的优劣。 第9 页 国防科学技术大学研究生院硕士学位论文 2 2 1 基于最小自由能方法 基于最小自由能方法的理论依据是，在热力学上，物体在稳定状态时，其自 由能最小。r n a 自然形成的二级结构应该是稳定的，所以r n a 自然形成的二级 结构应该具有最小的自由能。r n a 折叠的自由能最早是1 9 8 1 年由z u k e r 等提出 的，并且z u k e r 据此实现了m f o l d 算法【9 】 【1 1 1 。在过去的二十多年中，基础能量 模型已经被修改了多次。该方法通过动态规划方法计算具有最小自由能的r n a 二级结构。现在许多算法都是在m f o l d 算法的基础上实现的，经过多年的发展与 改进，m f o l d 算法已经非常完善，成为了r n a 二级结构预测算法中的经典算法。 下面详细介绍一下m f o l d 算法。 r n a 二级结构预测的实质是确定r n a 序列所有碱基的配对关系。其原因是 碱基配对是降低r n a 能量的唯一因素。根据这个原理，n a s s i n o v 8 】最早引入动 态规划算法到r n a 二级结构预测领域。n a s s i n o v 通过动态规划算法计算r n a 序列具有最多碱基配对数目的结构。在n a s s i n o v 的算法中，只使用了一个矩阵 m ( i j ) 来存储序列s i s j 中包含的最大碱基配对数，其计算公式如下： f o ，女尉蚺1 m ( i ，) = m ( i ，j f - 1 ) im i n ( m ( i ，七一1 ) + m ( 七+ 1 ，j - 1 ) + 1 ) ，当存在碱基配对( 后，) 在r n a 二级结构中，未配对碱基形成的环具有提高结构能量的作用，并且 相邻的碱基配对之间还会相互影响形成堆积。由于n a s s i n o v 没有考虑这些因素， 导致预测出来的结构有很多冗余的碱基配对。 其后，在n a s s i n o v 算法的基础上，z u k e r 等考虑碱基配对之间的相互作用以 及未配对碱基形成的环之间的相互作用，将二级结构划分为六种模体，把二级结 构看做这些模体的组合，并据此设计了算法m f o l d 。自此，最小自由能方法开始 在r n a 二级结构预测领域兴盛起来。 m f o l d 算法的前提是，假设组成二级结构的各个模体的自由能具有可加性和 相对独立性，即一个二级结构的自由能是组成它的模体的自由能之和，并且这些 自由能之间是互不影响互不关联的。m f o l d 算法使用动态规划算法从局部到整体 计算r n a 二级结构的最小自由能，然后通过回溯计算得到具有最小自由能的结 构。在计算过程中，m f o l d 主要使用了两个矩阵w ( i , j ) 和v ( i , y ) 记录结构的自由 能。形g _ ，) 存储序列s i s j 形成最优结构的最小自由能，当计算到w ( 1 ，刀) 后， 通过回溯这个矩阵就可以得到具有最小自由能的二级结构；y g _ ，) 存储碱基s i 第1 0 页 国防科学技术大学研究生院硕士学位论文 和s j 形成配对f 时，序列s i 形成最优结构的最小自由能。矩阵w ( i ，j f ) 和 v ( i ，歹) 的计算公式如下： w ( i ，) = v ( i ，) w ( i + i ，j f ) w ( i ，j - 1 ) m i h ( 形( f ，七) + 形( 七+ l ，歹) ) l 弗 2 i m i n ( 形( f + 1 ，七) + w ( k + l ，- 1 ) ) il + 、 、，一i 其中，函数h l ( i j ) 表示以碱基配对i j 封闭的发卡环的能量，函数s t ( i , j ) 表示 碱基配对i j 的堆积能量，函数i l ( i ，i j j ) 表示以碱基配对i j 和碱基配对i j w ( i j ) 和v ( i j ) 的计算可以表示成如图2 5 【1 0 】的形式。其中w ( i j ) 的值取等式 右边四种情况的最小值，第四种情况i 和j 形成碱基配对时的值即是v ( i j ) 。v ( i j ) = di 厶l 丛l 厶 iw ( i ，j ) ji j - 1j ii + l j ik j i j 么i 么6 i 么x l i v ( i ，j ) j i j ik1 j ik j 图2 5 m f o l d 算法中w ( 巧) 和v ( i j ) 的表示 为了方便计算每个模体的自由能，m f o l d 算法定义了四个自由能函数来分别 计算茎环、发卡环、内环和多分支环的能量，因为目前还不太清楚多分支环对 r n a 稳定性的具体影响，为了计算方便，通常情况下认为多分支环的能量取决 第1 1 页 国防科学技术大学研究生院硕士学位论文 与各个环的长度、碱基配对的数目以及起到稳定作用的摆动碱基。 m f o l d 中各模体的能量值都有表可查。由于多分支环多样性和复杂性，实验 上测定它们的具体自由能很困难，所以目前大都根据经验对其进行近似处理了。 除此之外，m f o l d 中各种子结构的能量参数基本上都是经过实验测定的。 m f o l d 算法的时间复杂度为o ( n 4 ) 。s m i t h 等人口8 1 以及l y n g o 2 9 1 等人对内环和 凸起环的长度做了限制处理后，最小自由能算法的时间复杂度和空间复杂度分别 降为d ( n j ) 和0 ( n z ) 。 m f o l d 算法不能预测伪结。r i v a s 等人在m f o l d 算法的基础上，引入了缺口 矩阵，提出了含伪结的简化能量模型，并首次提出基于该简化模型的动态规划预 测算法p k n o t s 1 2 】。p k n o t s 算法能够处理的伪结类型丰富，时间复杂度为o ( n 6 ) ， 空间复杂度为o ( n 4 ) 。p k n o t s 算法的时间复杂度偏高，b l y n g s j p 等人【1 4 】和李恒武 等人对伪结类型和环长度进行了限制，将时间复杂度降为o ( n 5 ) ，空间复杂度降 为o ( n 3 ) 。 p k n o t s 算法为使用最小自由能方法预测含伪结的r n a 二级结构开启了一条 新的道路，可以说是r n a 结构预测研究中的一个里程碑。 j e n sr e e d e r 等人【1 6 】【5 0 】在m f o l d 算法基础上，以m f o l d 算法为模版，将伪结 也看做是一种模体，即把伪结等同于茎环、凸起环、内环、发卡环和多分枝环， 然后通过近似计算伪结的能量，将其加入到动态规划算法的计算中，并设计了算 法p k o n t s r g 。 j e n sr e e d e r 使用七个参数计算伪结的最小能量( 如图2 6 【5 0 1 ) 。当对预测的 伪结类型和伪结内环长度做了限制以及对算法做了处理之后，这七个参数简化为 四个参数。由于j e n sr e e d e r 对二级结构各种子结构的能量做了深入研究，特别 是对伪结中环的能量有比较精确地认识，所以算法的平均预测性能是目前所有基 于最小自由能的动态规划算法里面最好的。算法的时间复杂度为o ( n 4 ) 。 ek gf 图2 6p k n o t s r g 中伪结计算模型图 第1 2 页 国防科学技术大学研究生院硕士学位论文 基于最小自由能方法预测r n a 二级结构的主要问题在于两方面。一方面是 时间复杂度过高，特别是针对含伪结的r n a 二级结构，这在很大程度上限制了 该方法的实际应用；另一方面是能量参数不精确，多分支环和伪结的能量参数现 在只有近似的数值，这严重影响了含伪结r n a 二级结构预测算法结果的准确率。 2 2 2 比较序列分析方法 比较序列分析方法的理论依据是，在分子生物学上，生物同源分子的结构保 守性一般大于序列保守性。在r n a 分子中这一点体现的更加明显。这就意味着 在物种进化过程中，即使r n a 序列的个别碱基发生变化，r n a 二级结构也很可 能保持不变。即当配对的某个碱基发生变异时，为了保持原有的配对，与之配对 的另一个碱基也随之改变，这就是协变现象。 比较序列分析方法利用协变现象，以同源i 矾a 家族序列作为输入，通过度 量同源r n a 家族序列间碱基的协变关系，推断出它们公共的二级结构 【1 7 】f 2 1 】【3 0 】【3 1 1 1 4 9 1 。常用的协变关系度量方法有互信息伫0 1 和协变信息【1 7 1 1 9 1 1 2 1 1 两种。 由于协变信息中考虑了碱基配对情况，一般比互信息更能体现协变现象，所以现 在大多数算法都是用协变信息模型。i 和j 两个位点之间的协变信息得分可用下 式表示： c , j = 厶( 删胛j - y t ( y y ) x y x y j c i j 表示n 条同源序列i 和j 两个位点的协变信息得分；f i j ( ) ( y ) 表示同源序列 中i 和j 两个位点出现配对x y 的频率；d x v 。x , v , 表示碱基对x y 与x y 的海明距 离矩阵，定义如下： f 0 胛叠p 或者x p 芒p 或榭= x y d x y r 二 lx y 萑e j ；l r q x 、屿r 仅有一者不等 i2 当x y 萑尸且一y 萑咄义且y y 其中p = a u ，u a ，c g ，g c ，g u ，u g 。 目前，基于比较序列分析方法的典型算法有r n a a l i f o l d 1 7 1 、c o n s t r u c t 3 1 1 、 p f o l