RNA二级结构预测算法的研究与实现优秀毕业论文.pdf

工学硕士学位论文工学硕士学位论文 rna 二级结构预测算法的研究与实现二级结构预测算法的研究与实现 夏培明夏培明 哈尔滨工业大学哈尔滨工业大学 2008 年年 6 月月 国内图书分类号：国内图书分类号：tp301.6 国际图书分类号：国际图书分类号：681.3.066 工学硕士学位论文工学硕士学位论文 rna 二级结构预测算法的研究与实现二级结构预测算法的研究与实现 硕 士 研 究 生：硕 士 研 究 生：夏培明夏培明 导师：导师：张岩张岩 副教授副教授 申申 请请 学学 位：位：工学硕士工学硕士 学 科 、 专 业：学 科 、 专 业：计算机科学与技术计算机科学与技术 所 在 单 位：所 在 单 位：计算机科学与技术学院计算机科学与技术学院 答 辩 日 期：答 辩 日 期：2008 年年 6 月月 授予学位单位：授予学位单位：哈尔滨工业大学哈尔滨工业大学 classified index：tp301.6 u.d.c.：681.3.066 dissertation for the master degree of engineering research and implementation of rna secondary structure prediction algorithm candidate： xia peiming supervisor: associate prof. zhang yan academic degree applied for：master of engineering specialty： computer science and technology affiliation: school of computer science and technology date of defence： june, 2008 university： harbin institute of technology 哈尔滨工业大学工学硕士学位论文 摘要摘要 rna（脱氧核糖核酸）是生物系统内最为重要的分子之一，它在生物 体内行使多种功能。预测 rna 二级结构具有重要意义，知道了 rna 的二 级结构就可以获得许多有益的信息，不仅能使我们更细致的了解各类 rna 在细胞中的运作机制，而且可以为寻找新的基因、治疗疾病提供帮助。 rna 的一级结构用实验的方法容易测定，但是由于 rna 分子具有降解速度 快、难以结晶等特点，故通过 x 射线晶体衍射和核磁共振（nmr）等实验 方法去测 rna 分子的空间结构很不容易，这样费时费力还代价高昂，虽然 测得的结果比较精确可靠，可是面对当前海量的生物序列，这种方法显然是 跟不上要求的。故而像蛋白质结构研究一样，借助于计算机手段和各种数学 方法从理论上去预测 rna 空间结构，是提高我们认识 rna 空间结构效率 的一个捷径，也是我们应当主要依靠的方法。 本文对 rna 二级结构预测问题进行了详细的阐述，并在充分汲取现有 预测方法优点的基础上，创新性地提出了两种 rna 二级结构预测算法，有 效地提高了预测的精度。 具体地，本文的主要研究内容和创新点如下： 首先，介绍了 rna 二级结构预测方法，包括问题的数学模型、测试数 据来源以及当前主流算法和软件。同时还说明了这些软件的优缺点及各自的 使用范围。 其次，介绍了 rna 二级结构预测中比较经典的最小自由能算法，分析 了其优缺点以及使用情况。在此基础上提出了基于茎区的动态规划算法来预 测 rna 二级结构，并结合茎区树的结构实现了假结的预测，然后将本算法 与最小自由能算法进行了对比实验分析，实验结果证明，本算法提高了预测 的精度，降低了时间复杂度。 第三，提出了一种基于随机上下文无关语法模型的算法来预测 rna 二 级结构及其假结。通过搜索茎区池寻找最优子结构来设置语法的生成概率， 使用 bestfirstsearch 搜索策略来寻找最大概率的语法推导路径，并使用动态 规划的思想来降低时间复杂度，实验结果表明算法的预测精度有所提高并能 够预测假结。 第四，实现了一个 rna 二级结构预测系统，该系统集成了本文中提出 的 rna 二级结构预测算法。 -i- 哈尔滨工业大学工学硕士学位论文 最后，本文对 rna 二级结构预测的前景进行了展望，探讨了该领域进 一步的研究方向。 关键词 关键词 rna 二级结构预测；动态规划；随机上下文无关语法；假结 -ii- 哈尔滨工业大学工学硕士学位论文 abstract rna（ribonucleic acid）is one of the most important molecule in our bodies and it has multiple functions. rna secondary structure prediction is of great significance. we will get lot of useful information if we know the structure of rna. not only enable us to understand rna operation mechanism with more detail, but also help to find new genes or treat diseases. rna sequence can be easily determined by experimental methods. however, due to the fast degradation and hard crystallization of rna molecules, it is not that easy to determine rna secondary structure by x-ray diffraction or nmr （ nuclear magnetic resonance）methods. it is difficult, slow and expensive. moreover, it is currently impossible to crystallize most rnas. so like the research of protein, it is very necessary to develop mathematic and computational methods to predict the secondary structure of rna. the research of this paper puts its emphasis manly on rna secondary structure prediction problem. by fully taking advantages of popular method, two new methods are proposed in this paper to improve the accuracy of the rna secondary structure prediction results. the creativities and contribution are discussed in detail as follows: firstly, the methods to predict rna secondary structure are introduced, including the mathematic models, free rna secondary structure databases, main algorithms and softwares. then seven popular softwares are compared to show their advantages, disadvantages and their scope of application. secondly, minimum free energy algorithm is introduced which is a classic method to predict rna secondary structure and analysis its advantages and disadvantages. based on this we propose helix-based dynamic programming algorithm to predict rna secondary structure which can predict pseudoknots combined helix tree. then this algorithm is compared to the minimum free energy algorithm in experiments. experiments prove that the modified algorithm performs better than the original algorithm. thirdly, a scholastic context-free grammar based algorithm is proposed to predict rna secondary structure including pseudoknots. the production -iii- 哈尔滨工业大学工学硕士学位论文 possibility is determined by searching helix pool to find optimal substructure. we use bestfirstsearch strategy to find the grammar derivation tree with greatest possibility. experimental results show that the accuracy of the prediction result is raised and the time is shorted. fourthly, based on the above algorithms, we developed an rna secondary structure prediction system. finally, this paper looks forward to rna secondary structure prediction prospect and some vital aspects that may be conducted in the future investigations are discussed. keywords rna secondary structure prediction, dynamic programming algorithm, scholastic context-free grammar, pseudoknots -iv- 哈尔滨工业大学工学硕士学位论文 目录目录 摘要 . i abstract.iii 目录 .v 第 1 章 绪论.1 1.1 课题背景.1 1.1.1 rna二级结构预测的目的和意义 .1 1.1.2 课题来源.2 1.2 国内外研究现状 .2 1.2.1 基于最小自由能的算法 .2 1.2.2 比较序列分析方法 .4 1.2.3 智能化的启发式算法 .5 1.3 目前主要rna二级结构预测软件的比较.6 1.4 问题的数学描述及本文的主要研究内容.8 1.4.1 问题的数学描述 .8 1.4.2 本文的主要研究内容 .10 1.5 本文的组织结构 .11 第 2 章 改进的动态规划算法预测rna二级结构.12 2.1 动态规划算法预测rna二级结构 .12 2.2 基于茎区的动态规划算法预测rna二级结构及假结.14 2.2.1 基于茎区的动态规划算法 .14 2.2.2 能量模型.16 2.2.3 茎区树来预测假结 .16 2.2.4 算法的流程 .19 2.3 实验结果分析.20 2.3.1 算法评价准则 .20 2.3.2 改进前后的动态规划算法预测结果比较及分析 .22 2.1.1 改进后的动态规划算法时间复杂度分析.26 2.4 本章小结.28 第 3 章 随机上下文无关语法预测rna二级结构及其假结.29 3.1 已有的语法模型 .29 -v- 哈尔滨工业大学工学硕士学位论文 3.2 随机上下文无关语法预测rna二级结构.31 3.2.1 随机上下文无关语法模型 .31 3.2.2 语法生成概率 .33 3.2.3 bestfirstsearch策略寻找最优二级结构 .35 3.2.4 后处理.38 3.3 实验结果及分析 .39 3.4 本章小结.44 第 4 章 rna二级结构预测原型系统 .45 4.1 引言.45 4.2 系统实现所用技术 .45 4.3 系统功能模块.45 4.3.1 数据输入模块 .45 4.3.2 二级结构预测模块 .46 4.3.3 预测结果分析模块 .47 4.3.4 预测结果显示和保存模块 .48 4.4 数据处理流程.49 4.5 本章小结.51 结论 .52 参考文献.54 哈尔滨工业大学硕士学位论文原创性声明.58 哈尔滨工业大学硕士学位论文使用授权书.58 致谢 .59 -vi- 哈尔滨工业大学工学硕士学位论文 第第1章 绪论章 绪论 1.1 课题背景课题背景 1.1.1 rna 二级结构预测的目的和意义二级结构预测的目的和意义 生物系统中基本的高聚物就是蛋白质和核酸，rna（脱氧核糖核酸） 是生物系统内最为重要的分子之一，它在生物体内行使多种功能，尤其在 hiv等病毒体中，遗传信息由rna而不是dna携带1。虽然真核和原核细胞 的遗传信息存储在dna（核糖核酸）中，但rna在基因表达中同样起着重 要作用。rna已经从简单的、线性的、功能单一的形象演变成今天种类多 样、结构复杂、功能特异的新形象，并且逐渐在中心法则中取得了与dna 和蛋白质同等重要的地位。尤其是上个世纪 80 年代中期，对于具有催化性 质的rna的惊人发现，使人们对于rna的研究逐渐升温。 rna 的功能与结构是密切相关的，rna 许多功能的实现需借助一定的 二级结构，甚至是三级结构。rna 序列也称为 rna 的一级结构，rna 的 空间结构被称为三级结构，rna 二级结构介于一级结构和三级结构之间， 要预测 rna 的三级结构比较困难，一般是先预测其二级结构，然后根据二 级结构再预测三级结构，因而预测 rna 二级结构对于预测 rna 的三级结 构具有重要意义。知道了 rna 的二级结构就可以获得许多有益的信息，不 仅能使我们更细致的了解各类 rna 在细胞中的运作机制，而且可以为寻找 新的基因、治疗疾病提供帮助。对于 rna 结构知识的掌握，为研究开发靶 向核糖体或病毒 rna 的药物提供了广阔的前景。目前这一领域已经引起了 越来越多的重视，某些 rna 二级结构的折叠算法已经被广泛用于药物设计 的研究。 rna 的一级结构用实验的方法容易测定，但是由于 rna 分子具有降解 速度快、难以结晶等特点，故通过 x 射线晶体衍射和 nmr 等实验方法去测 rna 分子的空间结构很不容易，这样费时费力还代价高昂，虽然测得的结 果比较精确可靠，可是面对当前海量的生物序列，这种方法显然是跟不上要 求的。故而像蛋白质结构研究一样，借助于计算机手段和各种数学方法从理 - 1 - 哈尔滨工业大学工学硕士学位论文 论上去预测 rna 空间结构，是提高我们认识 rna 空间结构效率的一个捷 径，也是我们应当主要依靠的方法。 1.1.2 课题来源课题来源 基金项目：国家自然科学基金（no. 60671011） 。 1.2 国内外研究现状国内外研究现状 rna二级结构预测问题，根据情况的不同衍生了不同的预测思路，不 同的研究学者也都提出了不同的预测方法。上世纪 70 年代到 80 年代初， tinoco提出了最小自由能模型2，nussinov和zuker等人针对该模型使用动态 规划算法来寻找rna折叠的最优结构，在不包含假结的情况下达到了比较 好的预测效果；当有一定的已知的rna二级结构信息作为先验知识的情况 下，可以通过比较序列分析多个同源rna序列，然后确定该组同源序列的 一致结构，进而确定未知rna序列的二级结构，基于这种思想的方法称为 比较序列分析方法,研究和大量实验表明，比较序列分析方法预测的结果准 确率更高 3；常规的方法不能预测出rna结构中的假结，假结已经属于 rna三级结构的范畴，为了预测假结，又有一些智能化的启发式算法相继 被用来解决这个问题，比如遗传算法43、人工神经网络算法33,41,42等等， 这些算法能够在一定程度上预测出假结结构，对于rna三级结构的预测有 一定的参考价值。 实验预测结果的准确率通常由两个参数确定，即敏感性（sensitivity） 和选择性（selectivity）4。目前衡量一种预测方法效果时通常使用这两个 参数，不过敏感性和选择性通常会出现此消彼涨的现象，因此又引入了另一 个参数马休兹相互作用系数（mcc）来均衡它们。下面依次详细介绍这些 问题。 1.2.1 基于最小自由能的算法基于最小自由能的算法 当没有任何先验知识，只给定了一条 rna 的一级序列时，预测 rna 的二级结构一般都会采用最小自由能模型。在该模型中，rna 二级结构中 每段模体（motif）都有相应的自由能计算方法，茎区的自由能为负值，环 - 2 - 哈尔滨工业大学工学硕士学位论文 区的自由能为正值，茎区越长其自由能越小，可以认为配对的茎区使自由能 降低，未配对的环区使自由能升高，而配对的茎区维持 rna 二级结构的稳 定，因此，最小自由能模型就假定真实的 rna 会折叠成一个具有最小自由 能的二级结构。 基于这种思想，nussinov提出了最大碱基匹配对算法5，使用了一种简 单的动态规划方法来寻找一条rna序列在不含假结的情况下所能形成的具 有最多碱基对的二级结构，该算法只考虑了碱基对自由能的影响，忽略了碱 基对之间自由能的影响和环区的自由能，因此它的时间复杂度较低，为 o(n3)，其中n是rna一级序列的长度。由于nussinov算法假设rna二级结构 中所有的碱基对的能量都是相互独立的，因此它输出的碱基对通常是不连续 的，不能够形成茎区。 自由能的大小并不是和配对碱基的个数成线性关系，它与配对碱基的 类型有关（a-u、g-c还是g-u） ，还受到相邻碱基对的影响，并且对于凸 环、内环等模体其自由能的计算方法也不一样。基于这些考虑，zuker等人 将模体简单分类为茎区、凸环、内环和发卡环，对不同的模体采用不同的自 由能计算方法，然后使用动态规划算法将各个模体组合，找出一个具有最小 自由能的二级结构6。zuker的动态规划算法假定各个模体之间的自由能是 相互独立的，rna二级结构的自由能就等于各个模体自由能之和。由于 zuker最小自由能算法考虑了不同模体的自由能，因此其算法复杂度略高于 nussinov算法。原始的zuker算法的时间复杂性是o(n4)，空间复杂性为 o(n2)。 动态规划算法所预测出来的结果都是嵌套的结构，它不能预测假结， rivas和eddy提出了可以预测假结的动态规划算法7。他们把动态规划矩阵 加以推广，使用一种叫隔空矩阵（gap matrices）的结构来描述计算包含有 假结情况的rna序列。除了计算凸环、内环等模体的自由能，递归关系中 还加入了假结的自由能，因此在时间上和空间上都有比较大的消耗，由于一 个假结需要四个参数来描述，因此递归关系中假结一项需要四层循环来寻找 最优，故该算法的时间复杂度是o(n6)，空间复杂度是o(n4)。 上述动态规划算法得到的结果是自由能最小时对应的二级结构。而实 验证明，真实结构往往不是自由能最小的结构。而且，自由能迄今为止还没 有完全正确的计算规则8。为了解决真实结构与最小自由能结构不一致的情 况，zuker等人又提出了次优结构的概念9。他们认为：真实的二级结构的 自由能也许不是最小的，但也应该具有一个较小的自由能值以使其分子结构 - 3 - 哈尔滨工业大学工学硕士学位论文 相对稳定。因此可以认为设定一个阀值，与最小自由能相差值在该阀值以内 的所有二级结构都可能是真实的结构，将它们全部输出，送给生物研究人员 再鉴定。显然，阀值设定的越大，包容的二级结构越多，覆盖到真实结构的 概率越大，而生物人员再鉴定的花费也就越大；而阀值设定的越小，虽然节 省了再鉴定的花费，但却增加了漏掉真实结构的概率。因此阀值的选择要适 中。目前由mathews等人开发的基于最小自由能模型的软件rnastructure （针对windows操作系统）和dynalign10（针对unix和linux系统）都可以由 使用者自己设定阀值。 基于最小自由能模型来预测rna二级结构，其准确率还不能令人满 意。当容忍“碱基对滑移” （base pair slippage）时，mathews等人认为预测 不同rna的准确率可以达到 73%8。 1.2.2 比较序列分析方法比较序列分析方法 在生物实验中，要处理的数据集通常是一组或几组同源 rna 序列，在 这些同源 rna 分子中，结构保守性一般大于序列的保守性，这些 rna 通 常具有相似的结构，例如所有的 trna 分子都有着几乎相同的二级（三叶草 形）和三级（倒 l 形）结构，正是这种结构上的一致决定了它们在功能上 的一致。针对这个特点，利用比较序列分析法可以提高预测的准确率。 比较序列分析是对多条rna序列进行互补碱基的共变联配，在已知序 列的数据库中搜寻与被考察序列相似的序列，以此来推断未知序列的二级结 构。它通过多序列联配并结合各类统计分析和序列上下文语义分析，构建出 一个通用的二级结构模型，并经过多次训练使之更加优化。通常采用的模型 有两种：一种是共变模型11，实际上就是隐马氏模型的一个推广，可以看 作生成一组rna序列簇的代表序列的概率机器，只是它比隐马氏模型多了 一个分支和一个描述共变配对状态的情况；一种是随机上下文无关语法模 型，它首先需要人为写出随机上下文无关语法的规则，然后在已知结构的 rna数据库中进行训练，得到每条语法规则的概率，然后利用进化信息和 随机上下文无关语法，找到使每条序列概率最大的生成法则，即该序列对应 的二级结构。 比较序列分析法按照序列比对与结构预测的先后顺序又可以分为三 种：一种是先比对后预测，这种方法假定了结构的保守性大于序列的保守 性，基于这种思路的预测结果强烈依赖于多序列比对的效果，但针对保守区 - 4 - 哈尔滨工业大学工学硕士学位论文 的多序列比对也是一个棘手的问题，先比对后预测的主要软件有pfold12 ，13 和alifold14；一种是结构预测与序列比对同时进行，这种方法主要使用 skanoff算法 15，它结合序列比对和nussinov（最大碱基对）折叠进行循 环，该算法极度消耗计算资源（时间复杂度为o(n3m)，空间复杂度为 o(n2m)，其中n是序列的长度，m是序列的数量） 。因此，基于该算法的软件 foldalign16 ，17和dynalign10都限制了子结构的大小和形状；最后一种就是 先预测后比对的方法，这种方法要求得到大量的次优结构 作为一个理论上的预测方法，比较序列分析法是最值得信赖的一种方 法，其预测结果仅次于实验上用 x 射线或 nmr 测定的结构，对于假结和其 他一些三级结构也有比较好的效果，但是由于它是一种基于已有序列的先验 知识的预测方法，因此首先要拥有一定数量的 rna 序列信息，并且假定这 些序列属于同源分子，具有一致的二级结构和基本单元。对于小的样本或者 差异很大的序列，其预测结果就不大可靠了。另外，它们首先都要涉及一个 多序列联配的问题，多序列联配载目前来说还是一个比较棘手的问题，联配 的好坏直接影响着后面的预测结果，而且这是一个相当耗时和耗内存的过 程，因此限制了比较序列分析方法在长 rna 序列上的应用。 1.2.3 智能化的启发式算法智能化的启发式算法 对于传统的 rna 预测方法来说，假结的预测始终是一个难题。因此各 类启发式的优化算法如遗传算法、免疫算法、模拟退火算法、神经网络等， 由于这些方法的高效性、并行性和灵活性，它们也逐渐被应用到 rna 二级 结构预测问题上，尤其是利用这些方法来解决假结预测问题。 遗传算法和免疫算法都是模拟生物系统中的进化规则，首先将 rna 二 级结构预测问题进行编码，然后在解空间中按照优胜劣汰的法则逐步求解或 接近最优解。神经网络算法是基于生物学中神经网络的基本原理而建立起来 的，它用一系列输入值及其加权来模拟一个神经元的判断或反应行为，输入 值和其关联权的内积表示神经元接受的信息。当把神经元分层排列，同层神 经元之间没有信息交流，计算按照一层一层同步进行时就是前馈型神经网 络，主要用于分类或设别问题。若神经元之间相互作用成一个网络，计算按 照整体进行，则称之为反馈型神经网络，它实质上是一个动力系统问题，可 应用于组合优化问题。 但是，这些方法都有一个共同的缺点，就是他们都是一种随意性很大的 - 5 - 哈尔滨工业大学工学硕士学位论文 黑箱方法，无法保证收敛到全局最优解，而且也无法判断出所预测的结果是 否接近最优解。所以，它们通常都是最为一种辅助的方法与其他方法结合起 来使用。 1.3 目前主要目前主要 rna 二级结构预测软件的比较二级结构预测软件的比较 rna二级结构预测发展速度很快。ncbi提供了大量rna序列数据，然 而提供结构的数据库并不多。目前用来为预测算法提供测试数据的结构数据 库主要有四个，分别是trna数据库18 ，19、rnase p数据库20、gutell实验室 比较rna站点和pseudobase假结数据库。如表 1-1 所示。由于目前大多数预 测算法还不能够很好地处理长度在 1k左右的长rna分子，因此大部分研究 者都采用trna和gutell比较站点所提供的数据来测试他们的算法或者软件。 表 1-1 可以免费获得 rna 二级结构的数据库列表 table 1-1 list for free rna secondary structure databases 数据库名称 网址 备注 trna 数据库 /gtrnadb/ 长度大多在 70nt 到 80nt rnase p rna 数 据库 /rnasep/home.html /rnasep/home.html 长度大多在 300nt 到 400nt gutell 实验室比 较 rna 站点 / 有更长的 rna， 需免费注册后才 可使用 pseudobase 假 结数据库 http:/www.biology.leidenuniv.nl/batenburg/pkb get.html 有很多假结数据 目前rna二级结构预测软件和提供在线预测的网址很多，本文列举了七 个主要的软件。分别是：rnafold14，mfold21，srna22，carna23,24， marna25，pfold12,13和rnastructure10。这七种软件被公认为效果比较 好，很多rna结构预测相关的论文都与它们其中的几个进行对比。本文对 这七种软件进行了分析，介绍了其主要预测原理，总结了各自的优点和局限 性，如表 1-2 所示。 - 6 - 哈尔滨工业大学工学硕士学位论文 表 1-2 各种主要的 rna 二级结构预测软件比较 table 1-2 comparison of popular software for predicting rna secondary structure 软件名称 优点 限制 原理 alifold/rnafol d 1. 提供选择是否支持 gu 配 对的选项； 2. 提供选择茎区边缘是否支 持 gu 配对的选项； 3. 容纳错误字符; 4. 可以预测单一序列，也可 以预测多条序列； 1. 预 测 单 个 序 列 时 长 度 不 能 超 过 300nt； 2. 预 测 多 个 序 列 时 ， 只 能 给 出 一 致 结 构 ， 不 能 预 测 每 一 个 序 列 的 二 级 结 构； 预测单一序列 依靠最小自由 能模型；预测 多个序列依靠 比 较 分 析 模 型； mfold 1. 可以人为设定先验知识； 2. 支持环形 rna 的预测； 3. 可以设置内环/凸环的最 大值； 4. 可以设置内环的最大不对 称值； 5. 可以设置碱基对之间的最 大距离； 6. 提供图形化输出； 只 能 预 测 单 个 序 列； 最小自由能算 法； srna 1. 提供反转功能； 2. 可以设置碱基对之间的最 大距离； 3. 可以人为设定先验知识； 4. 每次提供多个可选的结 构； 5. 图形化输出二级结构，街 面友好； 1. 只 能 预 测 单 个 序列； 2. 序 列 长 度 不 能 超过 5000nt； 3. 预测速度慢； 统计方法结合 最小自由能模 型； carnac 1. 可以选择是否允许长度为 1 的茎区存在； 2. 图形化输出二级结构； 每 个 序 列 长 度 为 80； 比较序列分析 法； marna 带有多序列比对功能，而且 序列比对和结构预测中的绝 大多数参数都可以由用户自 行设定； 多个序列的总长度 不能超过 10000nt； 先使用最小自 由能算法折叠 序列，然后进 行序列比对； pfold 输出结果的同时提供一棵进 化树； 不能预测假结； 上下文无关语 法模型； rnastructure/d ynalign 1. 操作界面友好，功能强 大； 2. 良好的图形界面输出； 输 入 字 母 表 只 有 acgu，其他字母或 者小写字母会被认 为是单链区； sankoff算 法 和最小自由能 算法； - 7 - 哈尔滨工业大学工学硕士学位论文 1.4 问题的数学描述及本文的主要研究内容问题的数学描述及本文的主要研究内容 1.4.1 问题的数学描述问题的数学描述 为了更清楚的介绍本文中的算法，首先给出以下几个定义： 定义 1-1 rna 序列 rna 序列又称为 rna 的一级结构，是由四种碱 基 a、c、g、u 组成的，可以用一条四个字母组成的字符串来表示 rna 序 列： s = s1s2sn，其中si a，c，g，u，i=1，2，n。 s表示整个rna序列，si表示rna序列中的第i个碱基，si,j表示rna序列中 第i个到第j个碱基的子序列，编号的顺序是从rna的 5端到 3的顺序。 定义 1-2 规范碱基对 rna序列中碱基与碱基之间可以形成配对，碱 基对一般有三种，c-g（g-c） ，a-u（u-a）和g-u（u-g） 。其中c-g（g- c）和a-u（u-a）被称为watson-crick碱基对。g-u（u-g）也经常出现在 rna二级结构中，以上这三种类型的碱基对都被称为规范碱基对1。 定义 1-3 相容的 一般用(i，j)来表示第 i 个碱基和第 j 个碱基形成的碱 基对，两个碱基对(i，j)和(i,j)是相容的，则必须满足下列条件之一： 1）两者是同一个碱基对，即 i=i，j=j。 2）(i，j)在(i,j)之前或者(i,j)在(i，j)之前，即或者。 ijijijij 3）(i，j)包含(i,j),或者(i,j)包含(i，j)，即ii或者。 jjiijj 定义 1-4 茎区 在 rna 二级结构中，两段连续逆向配对的碱基形成的 区域称为茎区，可以用一个三元组(i，j，k)来表示一个茎区，其中 i 是茎区 的起始碱基位置，j 是茎区的结束碱基位置，k 是茎区的长度，子序列(i， i+1，i+k-1)和逆向子序列(j，j-1，j-k+1)中的碱基可以依次形 成规范碱基对，并且碱基 i+k 和碱基 j-k 不能形成碱基对。 定义 1-5 rna 二级结构 集合 r=(i，j)，1i3 - 8 - 哈尔滨工业大学工学硕士学位论文 定义 1-6 假结 如果 r 中包含了不相容的碱基对(i，j)和(i，j)满足 ，则称这个 rna 结构中包含假结。 iijj rna 的二结构是指 rna 一级序列中各个碱基之间的配对关系，预测 rna 二级结构通常也被称作折叠（fold）rna。在 rna 二级结构中，碱基 配对一般按照规范碱基对来配对。单个的碱基被认为是不稳定的，两段子串 形成连续的逆向配对的区域称为茎区（helix） ，茎区中间的未配对子串形状 像一个发卡环，因此把这段区域称为发卡环（hairpin loop） 。在分子进化的 过程中，由于突变的发生，茎区的内部会产生部分不配对的现象。当部分碱 基变异，导致茎区的两个子串中各有部分碱基不能配对，这时形成的结构被 称为内环（internal loop） 。如果茎区的一个子串中有部分碱基在进化过程中 消失或者加入，则原茎区中的一个子串会存在一段不能配对的区域，这种结 构称为凸环（bugle） 。多个茎区和未配对碱基围成一个封闭的环，这种结构 称为多分支环（multi loop） 。各种环的结构如图 1-1 所示。 图 1-1 茎区、发卡环、凸环、内环及多分支环示意图 f