含假结RNA二级结构图的语法及拓扑分类

摘要

RNA的生物学功能很大程度上决定子其三维空间结构。空间结构一般通过x射线晶体衍射和核磁共振等实验方法获得，但是实验方法技术难度高、耗资大且并非总是可行。因此理论预测：RNA空间结构就非常必要，它可以提高认识RNA空间结构的效率，还可以指引实验研究的方向。 RNA二级结构预测是其空间结构预测的关键。目前，最小自由能法是预测RNA二级结构最主要的方法，但二级结构内部假结的存在使得该方法是NP完全的，这类方法只能考虑具有一定结构特征的假结，从而将时间复杂度控制在多项式范围内。视结构特征的不同，复杂度从D(n3)到D(n6)不等，复杂度越高能预测的目标集也越广，目前不存在速度快、目标集广的“好”方法。本文以时间复杂度为O(n6)的Rivas与Eddy算法的目标集(R&E类)为全集，从文法和语言的角度提出了R&E类及其子类的弧图语法，并从拓扑学的角度将其分类，具体内容包括： 1.提出了弧图语法概念。RNA二级结构弧图是一种特殊的二级结构图，从最简单的弧图开始，按照一定的替换规则对弧图的小部件用较大的部件替换，从而得到一个弧图类。那些体现结构特征的最简单的弧图称为初始弧图，那些替换规则称为重写规则，初始弧图和重写规则两类要素构成弧图语法。给定弧图语法就决定着一个弧图类，该类称为弧图语言。弧图语法提供了一种把数量无限的弧图映射成为数量有限的语法要素的研究方法，且具有易扩展性。 2.给出了5个二级结构算法类的弧图语法。本文首先设计出.R&E类的弧图语法，以R&E类弧图语法的要素为全集，给出其自小至大的子集PKF类、L&P类、D&P类、A&U类的弧图语法，这几个类阀具有真包含关系，这种关系直观地从他们的弧图语法要素中体现出来。通过研究这5个二级结构类间的关系以及代表元素使全面掌握各类的内容成为可能。 3.得到了平面R&E弧图的语法判据。直观地以平面图的形式展示二级结构有着很广泛的需求，本文在他人研究的基础上在更大范围--R&E类内给出基于弧图语法的判别依据，同时给出了平面嵌入算法。通过可平面R&E类的弧图语法，在R&E类内部完全解决了可平面弧图的平面嵌入问题。在R&E类外部也进行了初步的探索，得到一些有益的例证。 4.实现了R&E弧图的书嵌入分类。RNA二级结构图的书嵌入自1999年提出以来由于其高时阈复杂性(NP完全)而一直停留在概念上。本文以R&E类的弧图语法为基础，以弧图的交叉关系图为桥梁，最终通过交叉关系图的极大团覆盖求出任意R&E弧图的书嵌入数并给出嵌入方案，将传统意义上的NP完全问题在R&E类上用多项式时间加以解决。 5.改进了计算R&E弧图亏格的方法。本文基于R&E类的弧图语法，提出弧图亏格计算的动态快速算法，该方法把二级结构图的有向闭曲面分类法中计算亏格的时间复杂度由线性提高到常数，在枚举小亏格弧图和计算多个相似二级结构弧图的亏格上具有较大优势。