RNA(核糖核酸)作为生物大分子具有十分重要的生物学功能,RNA结构预测是计算分子生物学的基本课题之一,也是当今国际研究热点。RNA结构预测中很多问题都是NP-难的,与其设计不出精确算法,不如去设计其多项式时间近似算法,去指导该类问题的生物应用。RNA三级结构是比较稳定的结构,而预测RNA三级结构需先预测RNA二级结构。预测RNA二级结构方法主要有序列对比分析法和最小自由能量法,序列对比分析方法预测RNA二级结构,是通过在不同生物有机体中起相同生物功能的一级结构进行比对得到RNA碱基序列的二级结构。许多生物有机体RNA分子的同源序列不易得到,需要耗费大量人力,因而序列对比分析方法的预测效率较低,利用最小能量方法来预测RNA二级结构是广泛采用方法之一Zuker提出的Mfold算法是早期基于最小能量方法来研究的二级结构预测算法,最小能量方法的本质是基于热动力学模型寻找RNA碱基序列所能形成的各种结构中具有最小能量的结构。Mfold算法的预测正确率为70%左右,但该算法不能预测假结和更复杂的结构,因而其应用受到较大限制。假结是RNA分子中最广泛的三级结构单元,是较复杂但稳定的RNA结构。假结在不同的RNA分子中具有构造、干扰、催化、调节等重要功能,包含假结的RNA预测是当今国际RNA结构预测研究的关键点和研究热点,预测包含任意假结的RNA二级结构问题是NP难的,至今未找到该问题有效的多项式算法,近似算法则为求解NP难问题的核心方法。连续基对构成堆叠,基对的交叉形成假结点,茎区的交叉构成假结结构,目前现有的预测含假结的RNA二级结构的算法,对较大的RNA分子计算很困难。基于茎区组合来寻找RNA优化结构成为包含假结RNA结构预测重要方法,Benedeti等人提出基于茎区组合的能量集合算法来预测RNA二级结构,Ruan等人提出基于茎区的启发式算法来预测包含假结的RNA二级结构,其时间复杂度为O)(n4),空间复杂度为O(n2)。本文根据RNA假结表示模型,基于RNA茎区结构相对稳定的特征和最小自由能量原理,提出了预测含假结的RNA二级结构的启发式算法,时间复杂度为O(n3)和空间复杂度为O(n2),通过在RNA假结库实验表明,该算法有较好的预测特异性和敏感性。连续堆叠可构成茎区,针对基于茎区的RNA优化结构,将序列划分为长度不大于t(t>2)的子序列,计算由长度不大于t的子序列构成的最优结构作为整个序列的近似结构,设计出预测任意假结的1+ε(ε>0)多项式时间近似方案(PTAS)。通过对假结加以限制来预测简单假结的最小能量算法是目前较多的含假结二级结构预测方法,Rivas和Eddy提出的Rivas算法使用预测任意的平面假结和部分非平面假结,其时间复杂度为O(n6)和空间复杂度为O(n4)。Jens和Robert提出的JR算法可预测简单的嵌套假结,时间复杂度为O(n4)时间,空间复杂度为O(n2)空间,Lyngs(?)和Pedersen使用相容结构代替Rivas算法中的缺口矩阵,提出了Lyngso算法,算法时间复杂度为O(n5)和空间复杂度为O(n3),但该算法仅能预测一个平面假结。连续堆叠形成茎区,堆叠和茎区是稳定RNA结构的主要作用,Cary和Storm提出的最大权匹配算法可以折叠RNA假结结构,但以预测正确率降低为代价。堆叠最大化问题也是近年来人们十分关注的含假结RNA二级结构预测问题。在平面RNA二级结构中,允许假结的存在使计算最大堆叠数问题成为NP难的,Ieong.S等人提出了最大堆叠基对数问题,设计了带任意假结的RNA二级结构预测近似算法,分别设计出平面二级结构的近似算法和普通二级结构的近似算法,并且证明了平面RNA二级结构中求含假结的最大堆叠数问题也是NP难的。分析了包含假结的RNA二级结构,剖析连续堆叠对和假结的结构特性,分析求解最大堆叠数的近似算法,其近似性能比为1/3,给出了证明,讨论了最大堆叠数问题的计算复杂性,并且可以预测更复杂的假结。给出RNA碱基序列S和正整数h,通过把三划分匹配这一NP难问题规约到该问题,判断在平面RNA二级结构中是否可能存在大于等于h的最大堆叠数,从而证明了在平面RNA二级结构中含假结的最大堆叠数问题也是NP难的。本文的主要工作为：1、基于最小自由能量的RNA结构的表示建模是RNA结构预测的关键。对于假结而言,可分为平面假结和非平面假结,假结可形成嵌套或并列结构,由两个茎区结构可形成嵌套假结,由内环和凸起可构成平面假结,平面假结经常出现在RNA分子中,交叉假结也存在于RNA中。茎区在RNA结构稳定性中承担着重要作用,基于茎区的交叉可形成假结的特性,可利用茎区结构建立关于假结的表示模型。在PseudoBase假结数据库中,大部分为平面假结,也包含少量的非平面假结。通过设计启发函数、用恰当的假结表示建模来预测RNA假结结构可取得较好的效果。根据RNA假结表示模型,基于最小自由能量原理,设计了预测任意平面假结和非平面假结的启发式算法,通过在PseudoBase等假结数据库实验验证表明,算法的预测敏感性特异性和预测准确度均有所提高,其时间复杂度为O(n3),空间复杂度为O(n2)。2、一般来说,连续的堆叠可形成茎区结构,茎区结构可使RNA结构能量降低,结构更稳定。通过茎区的组合优化特性来预测RNA优化结构是我们采用的重要方法,茎区之间可形成并列结构、嵌套结构和交叉结构。含有交叉结构即包含假结,假结的存在是RNA结构预测变得复杂,是问题难解性的重要因素,使得设计多项式时间算法变得异常困难,设计该问题的近似算法或近似方案成为处理该问题的重要手段。针对基于茎区的RNA优化结构,把RNA碱基序列用短茎进行划分,计算由长度不大于t的茎区构成的结构作为整个序列的近似结构,重新分析了预测任意假结的1+ε(ε>0)多项式时间近似方案。3、在RNA碱基序列中,连续的两个碱基对可构成堆叠,从堆叠的角度看,多个连续碱基对可形成连续堆叠,连续堆叠中堆叠的个数越多,则RNA结构越稳定。在RNA结构预测中,包含假结的计算最大堆叠数问题也是NP难的,针对该类问题,与其设计不出多项式时间精确算法,不如退而求其次,通过其内在特性的深入分析,设计求解该类问题的多项式时间近似算法。分析其近似性能比,尝试降低近似比,指导该问题的求解。针对连续堆叠对的结构特性,重新分析了RNA二级结构最大堆叠数问题,通过在RNA折叠结构中查找连续堆叠,并对内在特性加以剖析,分析了计算最大堆叠数的近似算法,其近似性能比为3,并给出了近似性能比的证明。本文下一步的主要工作包括：1、设计包含任意平面假结的RNA结构预测近似算法,降低近似性能比和时间复杂度。2、设计求解包含假结的普通RNA结构最大堆叠数近似算法,进一步降低近似性能比,降低时间复杂度。3、针对平面和非平面RNA假结结构,其结构特性和组合特性仍需深入剖析挖掘,期望设计出更精确的预测算法。