随着越来越多非编码基因及其功能被识别和揭示,人们逐渐认识到非编码RNA和蛋白质分子一样重要,甚至是主要的功能性分子。二级结构预测是非编码RNA识别及其功能研究的根本途径与核心基础,因此RNA二级结构预测方法的研究具有重要的科学意义。基于比较序列分析的RNA二级结构预测方法精度最高、效果最好、应用最普遍。在这一类方法中,算法的输入是一组同源RNA序列或由它们组成的RNA多序列比对,算法的目标是求出所有RNA序列共有的最优二级结构。目前,基于比较序列分析的RNA二级结构预测方法还存在以下五个问题:(1)如何降低二级结构检测或预测算法的计算复杂度,同时又能保证算法的精度?(2)如何设计基于生物知识的、启发式的二级结构预测算法?(3)如何构建高质量、高精度的RNA多序列比对,以提高二级结构预测的精度?(4)如何在二级结构预测算法中引入更多更详细的参考信息(如系统进化信息)以提高算法的精度?(5)如何在二级结构的预测过程中对得到的二级结构进行评估,从而给出精度更高、可信度更大的预测结果?本文针对以上问题进行了深入的分析和研究,分别提出和实现了相应的解决方法,并在相应的数据集上对它们进行了测试验证和比较分析。本文的主要工作和创新之处概括如下:(1)提出位置矩阵和位置向量的概念及理论。本文提出的位置矩阵是一种特殊的n×n矩阵,n为RNA序列或RNA多序列比对的长度,矩阵的类型有两种:单个RNA序列的位置矩阵和RNA多序列比对的位置矩阵。单个RNA序列的位置矩阵元素取值类型有三种:0、1、-1,通过检测矩阵的行中连续非0区域,可以方便准确地识别出RNA序列中连续碱基配对区域(即stem)。RNA多序列比对的位置矩阵元素取值类型有两种:0、1,通过检测矩阵的行中连续“1”区域,可以方便准确地识别出RNA多序列比对中保守的连续碱基配对区域(即保守stem)。本文提出的位置向量是一种特殊的n维向量,n为RNA序列或RNA多序列比对的长度,位置向量的类型有两种:单个RNA序列的位置向量和RNA多序列比对的位置向量。位置矩阵记录了RNA序列或RNA多序列比对的全部可能的折叠方式,位置向量则记录了RNA序列或RNA多序列比对在某种折叠方式下的具体二级结构。理论分析和数值实验表明,上述理论能够有效地帮助解决RNA二级结构预测中的若干相关问题。(2)提出基于信噪比度量的RNA二级结构评估方法。stem是RNA二级结构的最基本组成单元,本文以stem而非整个二级结构为建模对象,针对不同问题,提出不同的评估算法,并应用到相应问题的解决方法中。概括起来,本文提出的RNA二级结构评估算法可以分为两类:针对RNA序列中stem的评估算法和针对RNA多序列比对中保守stem的评估算法。对于前者,本文以stem中包含的碱基对个数为参考计算信噪比值Signal-to-Noise;对于后者,本文以保守stem中包含的所谓“列对”个数为参考计算信噪比值Signal-to-Noise。数值实验表明,这两类评估算法在相应问题的解决中均能有效地改善相应方法的性能。(3)提出基于多序列比对的RNA二级结构检测与评估方法。RNA二级结构检测是识别非编码RNA的关键过程,本文以RNA多序列比对为处理对象,采用比较序列分析策略,利用位置矩阵、位置向量理论和信噪比度量方法,提出基于保守stem检测与评估的RNA二级结构检测与评估算法。理论分析和数值实验表明,本文方法均优于主流方法QRNA和ddbRNA。与QRNA相比,本文方法具有计算复杂度低、适于RNA多序列比对(包含两条以上序列)和敏感性高等优点;与ddbRNA相比,本文方法具有敏感性和特异性均高、适于包含空位的RNA多序列比对等优点。(4)提出基于位置矩阵和位置向量的RNA二级结构预测方法。这是本文提出的位置矩阵和位置向量理论在RNA二级结构预测中的直接应用。首先,论文提出一种基于“种子-扩展”的启发式RNA二级结构预测方法;其次,论文提出一种基于保守stem检测与评估的混合式RNA二级结构预测方法。对于每一种方法,论文分别在不同的输入(RNA多序列比对或未比对的同源RNA序列集合)情况下,给出了不同的具体实现算法。对于每个算法,论文均给出了相应的数值实验和性能分析。实验结果表明:在以RNA多序列比对为输入的情况下,两种方法均优于同类方法RNAalifold;在以未比对的同源RNA序列集合为输入的情况下,两种方法均优于同类方法Mfold。(5)提出基于位置矩阵和位置向量的RNA多序列结构比对构建方法。构建高质量的RNA多序列结构比对是基于比较序列分析的RNA二级结构预测方法中关键步骤。本文以位置矩阵、位置向量理论和信噪比度量为基本方法,以“种子-扩展”为基本思想,以未比对的同源RNA序列集合为输入,提出一种基于保守stem检测与评估的RNA多序列结构比对构建方法。论文首先阐述了RNA序列的结构比对问题,然后给出了本文方法的详细描述,最后给出了该方法的数值实验和性能分析,实验结果表明:该方法明显优于当前主流方法Clustal W。(6)提出基于上下文无关随机文法和系统进化分析的RNA二级结构预测方法。系统进化信息是生物序列分析中重要的参考信息。本文通过把更加丰富、复杂的同源RNA序列系统进化信息融合到RNA二级结构预测过程中,提出一种新的混合RNA二级结构预测方法。首先,论文定义了新的剖面上下文无关随机文法,以实现对RNA多序列比对及其一致二级结构的建模;其次,论文定义了两个不同的隐马氏模型,分别对RNA序列的非结构区域和结构区域的系统进化过程进行建模;最后,论文通过把此二个隐马氏模型融合到新定义的剖面上下文无关随机文法中,提出一种新的全概率模型以计算最优一致二级结构。数值实验表明:本文提出的方法优于当前主流方法Pfold,尤其当输入的RNA多序列比对中包含的序列个数更多、空位更多、序列保守性更低时,这种优势更加明显。