论文摘要
RNA结构预测是计算生物学的基本课题之一。RNA二级结构预测是由RNA序列预测其三级结构的第一步。早期采用序列对比分析方法预测RNA二级结构,对于在不同有机体中起相同生物功能的一级结构进行比较得到RNA序列的二级结构。许多RNA分子的同源序列不易得到,需要耗费大量人力,因而序列对比分析方法的预测效率较低。目前人们广泛采用最小能量方法预测RNA二级结构。最小能量方法是基于热动力学模型寻找序列所能形成的各种构象中具有最小能量的结构。Zuker提出的MFOLD算法是目前应用较为广泛的二级结构预测算法,其预测正确率为73%左右。但该算法不能预测假结和更复杂的结构。假结（pseudoknot）是RNA中最广泛的三级结构单元,是较复杂但稳定的RNA结构。假结预测是目前RNA结构预测研究的关键点和研究热点。假结在不同的RNA分子中具有调节、催化、构造等重要功能。预测包含任意假结的RNA二级结构属于NP-hard类。预测简单假结的最小能量算法是人们讨论较多的含假结二级结构预测方法。Rivas和Eddy提出的PKNOTS算法使用O（n6）时间和O（n4）空间预测任意的平面假结和部分非平面假结,Jens和Robert提出的PknotsRG算法使用O（n4）时间和O（n2）空间预测简单的嵌套假结,Lyngse和Pedersen提出的LP算法使用O（n5）时间和O（n3）空间预测一个平面假结。组合优化算法只考虑RNA序列中的部分主要作用,如Cary和Storm提出的最大权匹配算法可以折叠RNA假结,但以预测正确率降低为代价。也有将遗传算法、模拟退火算法、神经网络算法应用到RNA假结预测中的计算尝试。相邻基对构成堆积（stack）,碱基配对和堆积作用是稳定RNA结构的主要作用。堆积最大化问题也是近年来人们十分关注的含假结RNA二级结构预测问题。Ieong等人于2001年提出最大堆积基对数问题,并设计出该问题的近似性能比为3的近似算法。Lyngse于2004年给出了最大堆积基对数问题的精确算法,并且提出最大堆积数问题,证明最大堆积数问题属于NP-hard类,给出了其多项式时间近似方案。Lyngsφ将所有堆积等同看待,但RNA结构实验的结果表明,不同类型的堆积有不同的能量,堆积的能量由构成堆积的基对类型所决定。因此我们基于生物学的碱基配对和基对堆积作用,提出了最大权堆积问题,并讨论最大权堆积问题的求解算法和计算复杂性。我们将堆积划分为（AA,BB）和（AB,BA）两类,利用（AB,BA）类构成团的特性计算其最优结构,利用堆积的划分特性计算（AA,BB）类的3/2近似的结构,取权值最大者作为整个序列的近似结构,给出了预测任意假结的多项式时间近似算法,其近似性能比为3,时间复杂度为O（nlogn）,空间复杂度为O（n）。我们将序列划分为长度小于K+1（2≤K）的子序列,使用动态规划计算和保存各类子序列的已配对权值和未配对子序列数,删除不可能结构和权值小的结构,计算长度小于K+1的子序列构成的最优结构作为整个序列的近似结构,给出预测任意假结的多项式时间近似方案。目前预测含假结RNA二级结构的多项式时间算法,难以计算大的RNA分子。连续的堆积构成茎（stem）,茎的交叉构成假结。因此基于茎区组合来寻找RNA最优结构成为新的RNA结构预测方法,如Benedeti等人提出的茎区堆积算法和李伍举等人提出的茎区随机堆积算法,预测嵌套的RNA二级结构。最近Ruan等人提出基于茎区的启发式算法预测包含假结的二级结构,其时间复杂度为O（n4）,空间复杂度为O（n2）。我们设计了一个预测任意假结的茎最大化的启发式算法。首先搜索序列可能构成的全部茎,找出具有最小能量的最大茎,然后在序列中标记最大茎对应的碱基,使其不再参与后面的配对,再在剩余的碱基中找出次最大茎,依次类推,直至无茎为止。该算法的时间复杂度为O（n3）,空间复杂度为O（n）,可以预测长度达5000个碱基的RNA序列。我们的算法使用茎代替基对,使用标记代替删除,消除了大量冗余基对和无意义的堆积,提高了预测的正确率。相对O（n3）时间和O（n2）空间的最大权匹配算法,其空间复杂度由O（n2）降至O（n）;实验表明其敏感性由80%提高到87.8%,特异性由53.7%提高到75.9%。与83.3%的预测正确率的遗传算法和79.7%的预测正确率的模拟退火算法相比,我们的算法将预测正确率提高到87.5%。最小自由能量方法预测RNA结构的关键是结构的表示建模。基于RNA分子茎区相对稳定的结构特征,我们引入半扩展结构和k茎,使用k茎计算半扩展结构,使用半扩展结构的交叉计算嵌套和交叉假结,建立新的RNA假结表示模型。平面假结是最广泛的假结子类,PseudoBase数据库中仅有一个非平面假结。基于新的RNA假结表示模型,我们引入假结同轴堆积作用,设计和实现动态规划算法,预测包含任意平面假结和简单非平面假结的RNA二级结构。使用该算法折叠PseudoBase假结数据库中的全部245个序列,173个序列的假结预测正确,其正确率为70.6%,敏感性为83.6%,特异性为76.6%;其中对于3′-UTR其它病毒类的84个序列,71个序列的假结预测正确,其正确率为84.5%,敏感性为91.0%,特异性为91.2%。实验结果表明该算法具有较好的假结预测正确率。与目前最好的PKNOTS算法相比,我们的算法计算的序列长度由140个碱基提高到800个碱基,其时间复杂度由O（n6）降低为O（n4）,空间复杂度由O（n4）降低为O（n3）。对于PKNOTS算法的测试序列,其敏感性由82.8%提高为84.8%,特异性由78.9%提高为80.7%。与计算简单的嵌套假结的PknotsRG算法相比,我们的算法可计算复杂的嵌套和交叉假结,而时间复杂度与PknotsRG算法相同。对PseudoBase数据库的测试表明,PknotsRG算法的假结预测正确率为68%,而我们的假结预测正确率为70.6%。与计算一个平面假结的LP算法相比,我们的算法将时间复杂度由O（n5）降低为O（n4）,并且可以预测更复杂的多假结。本文包括五部分内容和结果。在第一章中概述RNA结构预测的研究意义、研究现状和基本概念。在第二章中回顾和总结了已有的RNA二级结构预测算法和假结预测算法。在第三章中给出了最大权堆积问题的多项式时间近似算法和近似方案。在第四章中给出预测任意假结的茎最大化的启发式算法和实验结果。在第五章中给出预测平面假结的动态规划算法和实验结果。最后进行简要总结。本文的主要创新工作为:（1）基于碱基配对和堆积作用,提出了最大权堆积问题,设计了最大权堆积问题的O（nlogn）时间和O（n）空间的近似算法,其近似性能比为3。给出了最大权堆积问题的的多项式时间近似方案。（2）设计了O（n3）时间和O（n）空间的茎最大化的启发式算法,算法可以预测任意假结和长度达5000个碱基的RNA序列。相对O（n3）时间和O（n2）空间的最大权匹配算法,其空间复杂度由O（n2）降至O（n）,其敏感性由80%提高到87.8%,特异性由53.7%提高到75.9%。（3）建立了含有半扩展结构和k茎的RNA假结表示模型,设计了预测任意平面假结和简单非平面假结的动态规划算法,对PseudoBase数据库全部序列的预测敏感性为83.6%,特异性为76.6%。与目前最好的预测任意平面假结和部分非平面假结的PKNOTS算法相比,其时间复杂度由O（n6）降低为O（n4）,空间复杂度由O（n4）降低为O（n3）,计算的序列长度由140个碱基提高到800个碱基;对PKNOTS算法测试集合的预测敏感性由82.8%提高到84.8%,预测特异性由78.9%提高到80.7%。