论文摘要
RNA二级结构预测要求根据RNA序列计算序列中符号的配对集,使得配对集所形成的结构具有最小自由能量。如何得到更加准确的预测结构,是近三十年来生物信息学的热点之一。以往人们采用序列比对分析法获得RNA序列的准确二级结构,但是该方法人工工作量大,条件限制较多,因此无法广泛应用。目前热动力学最小自由能量方法已成为RNA二级结构预测的最常用方法。基于动态规划和最邻近能量模型的Mfold算法是计算RNA二级结构最小自由能量的经典方法。假结是RNA中普遍存在的二级结构单元。但Mfold算法不能预测假结。目前预测假结的最好算法是Rivas算法。该算法能得到最优平面假结结构和部分非平面假结结构,但算法的时间复杂度太高。本文首先实现和改进Mfold算法。基于环和最临近能量模型,使用实验室测量的能量数据,通过动态规划计算子链的最小自由能量,并且计算最优二级结构,实现Mfold算法。把同轴堆叠模型加入Mfold算法,从而得到具有更低的自由能量的RNA二级结构,实现Mfold算法的改进。改进算法的时间和空间复杂度与Mfold算法相同。我们通过实验比较了Mfold算法和改进算法,结果表明,相比Mfold算法,改进算法的预测准确度由76.43%提高到78.25%。然后本文实现了多折叠的次优算法。该算法首先把线性RNA序列抽象为环链,任意选择一个基对将环链划分成内段和外段,分别计算内段和外段的能量和结构。内段和外段的能量之和为次优能量,结构之组合为次优结构,其时间复杂度是O(n~3),空间复杂度是O(n~2)。次优算法为RNA二级结构分析提供更多有用的信息。随后本文给出了一个计算简单假结的二级结构算法。通过任意选择两个交叉的基对,把序列划分为五段,分别计算每一段的能量和结构,从而得到包含一个简单假结的二级结构。该算法的时间和空间复杂度与Mfold算法相同。最后,本文给出30余个实际序列的实验测试,进行对比分析和准确度计算。本文的主要创新点为:1.引入同轴堆叠改进Mfold算法,将Mfold算法的预测准确度由76.43%提高到78.25%。2.提出带人工干预的简单假结二级结构计算方法,其时间复杂度和空间复杂度分别为O(n~3)和O(n~2)。3.用Java语言实现了Mfold算法和Mfold改进算法,用30多个例子比较了两种算法的优劣。