多重序列比对上的RNA相互作用问题

摘要

在本篇论文中，我们主要讨论多重序列比对上的次优正则联合结构的预测，以及核糖核酸(RNA)的拓扑性质。
　　在第一章中，我们首先简要地介绍了核糖核酸之间相互作用问题(RIP)的背景。由于非编码核糖核酸(ncRNA)与它的目标核糖核酸通常连接在一起来完成基因的整个调节过程，因此研究它们之间相互作用的关键特性，就显得十分必要。接着我们综述了近些年来在该问题上的研究进展情况，并讨论了当前现有的一些预测算法各自的特性。最后我们对本文的主要内容作出概述，并给出相应的结果。
　　接着在第二章中，我们首先介绍了预测两个单核糖核酸序列上的联合结构所需要的基础知识，比如核糖核酸二级结构的表示、圈结构、组合性质以及它的能量模型。然后在两个单核糖核酸序列的基础上，我们介绍了联合结构的概念和它的分解语法，以及基于该分解语法上的配分函数的计算和联合结构的块概率。这些概念将在多重序列比对的预测算法中，起到至关重要的作用。在核糖核酸结构图谱不作限制的情况下，尽管它们之间的相互作用问题在[2]中已经被论证为是NP完全的，但如果我们在两个单核糖核酸序列上作一些约束，比如排除“之”字形结构，利用本章的方法，我们仍然能够得到多项式时间的动态规划算法。
　　我们在第三章中建立了一个基于多重序列比对的通用框架[26]。在该框架的基础上，我们开发了一个用C语言实现的折叠算法包ripalign。虽然它的目标是预测多重序列比对上的正则联合结构，但同时它也包含了rip[19][20]中的所有功能。除此之外，ripalign还允许输入的核糖核酸序列比对中包含结构的约束信息，这是rip所无法企及的。在第三章中，首先基于[19]中联合结构的概念，并根据栈和混合结构的长度，我们提出了正则联合结构和相容联合结构的概念。之后，我们研究了正则联合结构的能量模型，并给出相应的计算方法。接着我们主要致力于介绍正则联合结构的分解语法、配分函数的计算、玻尔兹曼取样以及多重序列比对上的碱基配对概率。最后，我们讨论了现有的一些其他预测算法，并对它们的性能进行了比较分析。
　　在第四章中，我们从拓扑的角度来表示核糖核酸的结构。首先利用线性弦图，我们对核糖核酸的结构建立拓扑模型，并根据亏格对它们进行分类。然后我们对具有任意亏格的影子集合进行计数。特别地，我们构造了亏格为2的影子和形态之间的一个映射，并计算出两者之间的数量关系。最后，我们提出了由亏格为g到亏格为g+1的影子生成算法。