含假结基于扩展结构的核糖核酸折叠结构预测方法与装置

摘要

本发明提供一种含假结基于扩展结构的核糖核酸折叠结构预测方法及装置，该方法包括以下步骤：随机输入一段核糖核酸碱基序列、定义假结和扩展结构、建立包含假结和扩展结构的核糖核酸假结结构特征模型和数学模型、计算出特征模型的最小碱基自由能量、输出包含假结的核糖核酸折叠结构；该装置包括输入单元、初始化单元、存储单元、计算单元和输出单元。本发明基于扩展结构进行计算，并且引入基于扩展结构的连续堆叠和同轴堆叠，有利于形成包括连续堆叠、扩展结构、环结构和假结结构的完整准确的RNA折叠结构，搜索速度、正确率、敏感性和特异性都明显好于现有技术，在平面假结和非平面假结结构的预测上比现有技术更有效。

说明书

技术领域

本发明涉及一种对核糖核酸(以下简称为RNA)的假结结构和扩展结构进行预测的方法，尤其涉及包含假结基于扩展结构的核糖核酸折叠结构预测的方法及装置，属于生物信息工程领域。

背景技术

核糖核酸(缩写为RNA，即Ribonucleic Acid)，RNA是以DNA的一条链为模板，以碱基互补配对原则，转录而形成的一条单链，存在于生物细胞以及部分病毒、类病毒中的遗传信息载体。RNA由核糖核苷酸经磷酸二酯键缩合而成长链状分子。一个核糖核苷酸分子由磷酸，核糖和碱基构成。RNA的碱基主要有4种，即A腺嘌呤、G鸟嘌呤、C胞嘧啶、U尿嘧啶。主要功能是实现遗传信息在蛋白质上的表达，是遗传信息向表型转化过程中的桥梁。

RNA是生物系统内最为重要的三类生物大分子之一，它在生物体内行使多种功能，是合成蛋白质的模板。RNA折叠结构预测用于蛋白质功能分析，是RNA三级结构预测的基础。假结(pseudoknot)是RNA中最广泛的结构单元，是非常复杂和稳定的RNA结构，假结在RNA分子中具有构造、催化和调节功能，假结结构是目前RNA结构预测研究的关键点。

RNA折叠结构预测采用的方法主要有两种：早期采用的是序列对比分析方法，即对于在不同有机体中起相同生物功能的一级结构进行比较，此方法的困难之处在于：许多RNA分子的同源序列不易得到；需要大量人力，效率较低，所以目前主要采用的是最小自由能量方法。最小自由能量算法的理论依据是稳定的折叠结构的自由能量最小。基于最小自由能量算法的PKNOTS算法使用O(n⁶)时间和O(n⁴)空间计算任意的平面假结和部分非平面假结。PKNOTS算法仅能计算长度短于140个碱基的RNA序列，不能满足较长序列结构预测的需要。PknotsRG算法计算两个茎区构成简单的嵌套假结，其中任意两个假结为并列或嵌套关系。事实上，由内环和凸起构成的假结在RNA中普遍存在，交叉假结也具有重要作用。因此，两者都不能被忽略。平面假结是最广泛的假结子类，包含由内环和凸起构成的假结以及交叉假结的情况。PseudoBase数据库的所有序列中仅一个序列折叠为一个非平面假结，其余序列都折叠为平面假结。因此我们主要考虑任意平面假结的计算。

Zuker首次将动态规划算法用于最邻近邻居模型提出MFOLD算法，经过二十多年的不断改进和发展，现己成为国际上最广泛使用的RNA折叠结构预测方法之一，对于包含n个核苷酸的RNA序列，MFOLD算法使用O(n³)时间和O(n²)空间预测最优折叠结构，目前对于长度小于700个核普酸的RNA序列，MFOLD算法可正确预测大约73％的基对，对于较长的RNA序列及部分子类的预测正确率更低，另外由于算法本身的限制，MFOLD算法不能预测假结和更复杂的三级相互作用，该算法应用存在很大局限性。

中国专利文献CN103235902A公开的一种包含假结的RNA结构预测方法，包括：确定待预测RNA序列中的所有结构单元，包括假结，把所有已知存在的结构单元放入结构单元池S₀＝{s₁，s₂，s₃，…s_n}，n为结构单元总数，s_n表示第n个结构单元；基于待预测RNA序列中的所有结构单元，通过迭代确定U＝{U₁，U₂，…，U_r，…，U_R}，Ur表示第r次迭代得到的RNA结构能量较小的RNA结构，R为总迭代次数；根据U_r中各元素的自由能及其在所有的RNA结构中出现频率的总和，分别确定Ur中各元素与实际RNA结构的相似值；将U中相似值高的元素预测为该待预测RNA序列的RNA结构。

CN104298894A公开的一种基于k茎的核糖核酸假结结构的预测方法及装置，包括以下步骤：输入一段核糖核酸碱基序列；定义假结、k(k≥1)茎；从左向右查找RNA碱基和k茎，对查找出的所有k茎进行确定标记；根据k茎的交叉形成假结的特性，查找假结；计算出包含k茎的核糖核酸假结结构的最小自由能量；输出核糖核酸的假结结构。

CN104765983A公开的一种基于半扩展结构的核糖核酸假结结构的预测方法及装置，包括以下步骤：输入一段核糖核酸碱基序列；定义半扩展结构；建立包含k茎和半扩展结构的核糖核酸假结结构表示模型和相应的最小能量的计算公式；根据最小能量原理，输出核糖核酸碱基序列的假结结构。

上述方法虽然在假结结构的预测方面比PKNOTS算法更有效，但是对假结的表示模型存在参数精度低、自由能量取值不准确，计算方法误差大等缺陷，使得在对假结结构预测方面的搜索速度、正确率、敏感性和特异性还没有达到理想的效果，有待进一步提高。

因此，有必要提出扩展结构的概念，并对两个核糖核酸序列片断s_i,k和s_l,j中的内部与外部的碱基配对规则加以规定，使其更接近真实结构，以解决包含假结的RNA折叠结构预测中参数精度低、自由能量取值不准确、计算方法误差大等缺陷，使搜索速度、正确率、敏感性和特异性得到明显提高。

发明内容

本发明针对现有技术存在的不足，提出一种含假结基于扩展结构的核糖核酸折叠结构预测方法，使得对包含假结基于扩展结构RNA折叠结构的预测时间复杂性和空间复杂性大为降低，搜索速度更快，正确率更高，而敏感性和特异性又有明显提高。同时提供一种实现该方法的装置。

本发明的含假结基于扩展结构的核糖核酸折叠结构预测方法，包括以下步骤：

(1)随机输入一段核糖核酸碱基序列，定义假结，定义扩展结构；

输入一段s＝s₁s₂…s_n序列，随机查找碱基，如果存在i、j，使得s_i和s_j配对，j-i≥3，并且s中存在三个以上连续的相邻基对s_i·s_j、s_(i+1)·s_k·s_l，则基对s_i·s_j和s_k·s_l封闭的区间确定为连续堆叠，对堆叠中所有配对的碱基进行标记；在连续堆叠封闭的游离碱基中继续查找配对的碱基，如果存在三个以上基对，确定为连续堆叠；如果存在两个以上连续堆叠的交叉，则构成假结；连续堆叠确定后，连续堆叠和包含游离碱基的两段碱基序列确定为扩展结构；假结点是由两对碱基对交叉配对而成；假结结构是由两个以上的连续堆叠或扩展结构交叉配对而成；

(2)建立包含假结和扩展结构的核糖核酸假结结构特征模型和数学模型；

(3)计算出特征模型的最小碱基自由能量；

(4)根据最小碱基自由能量原理计算结果，输出包含假结的核糖核酸折叠结构。

一个扩展结构由两个核糖核酸序列片断s_i,k和s_l,j构成，i<k<l<j。片断s_i,k和s_l,j交叉可形成假结结构。

所述两个核糖核酸序列片断s_i,k和s_l,j中，存在p和q，i<p<q<k，使s_p,q和s_l,j构成连续堆叠且片段s_i,k内部碱基之间不存在配对，即：若存在m和n且m<n,若(m,n)是碱基对，则m<i或n>k,或m<i且n<i,或k>m且k>n,则片断s_i,k和s_l,j构成扩展结构，用P[i,k:l,j]表示其最优扩展结构；或者是两个核糖核酸序列片断s_i,k和s_l,j中，存r和s，l<r<s<j，使s_r,s和s_i,k构成连续堆叠且片段s_l,j内部碱基之间不存在配对，即：若存在m和n且m<n,若(m,n)是碱基对，则m<l或n>j,或m<l且n<l,或k>j且k>j，则片断s_i,k和s_l,j构成扩展结构，用P[i,k:l,j]表示其最优扩展结构。

以下利用扩展结构和假结改进折叠结构的表示模型和连续堆叠的计算方法，优化计算参数。优化改进最邻近邻居Watson-Crick自由能量参数，假结能量参数和碱基配对堆叠参数取值。

W(i,j)为两个扩展结构碱基s_i和s_j不构成基对(i,j)时，子序列s_i,j对应的包含假结基于扩展结构的RNA折叠结构S的最小自由能量，计算W(i,j)的情况包括：(1)在扩展结构中s_i和s_j不参与构成堆叠，s_i和s_j是未配对碱基，s_i和s_j不构成基对(i,j)，且在不同子序列s_i,k和s_k+1,j对应的RNA折叠结构中，i<k<j；(2)s_i和s_j不构成基对(i,j)；s_i,j由一个扩展结构和一个子序列构成；或由两个扩展结构构成；或由两个扩展结构和一个子序列构成。

V(i,j)为在碱基s_i和s_j构成基对(i,j)时子序列s_i,j对应的包含假结基于扩展结构的RNA折叠结构S的最小能量，计算V(i,j)情况包括：S是在扩展结构中，基对(i,j)封闭的连续堆叠；或S是由在扩展结构中包含假结的基对(i,j)和(k,l)封闭的堆叠，i<k<j；或S是由在扩展结构中包含假结的基对(i,j)，(k,l)，(r,s),i<k<j,k<r<l封闭的堆叠，以此类推。

计算一个包含假结的扩展结构的情况包括：(1)一个扩展结构由另一个扩展结构和一个或几个未配对碱基构成；(2)一个扩展结构由另一个扩展结构和包含基对的子序列构成；(3)一个扩展结构由另外的两个扩展结构构成；(4)两个扩展结构交叉形成假结结构。

使用动态规划算法计算W(i,j)、V(i,j)和包含假结的扩展结构的最小自由能量。

实现上述方法的包含假结基于扩展结构的核糖核酸折叠结构的预测装置，包括：

输入单元：输入一段核糖核酸碱基序列；

初始化单元：定义假结，定义扩展结构；

存储单元：存储建立的假结模型和扩展结构的核糖核酸折叠结构特征模型，存储相应的最小碱基自由能量的参数、数据结构和计算公式；

计算单元：计算自由能量值和概率值；

输出单元：根据最小自由能量原理及出现统计概率，输出包含假结基于扩展结构的核糖核酸碱基序列折叠结构。

本发明提出了扩展结构的概念，基于扩展结构进行计算，精确定义了扩展结构，对两个核糖核酸序列片断s_i,k和s_l,j中的内部与外部的碱基配对规则加以规定，使其更接近真实结构，即存在p和q，i<p<q<k，使s_p,q和s_l,j构成连续堆叠且片段s_i,k内部碱基之间不存在配对，即：若存在m和n且m<n,若(m,n)是碱基对，则m<i或n>k,或m<i且n<i,或k>m且k>n。利用扩展结构和假结改进了折叠结构的表示模型和连续堆叠的计算方法，优化了计算参数。优化改进了最邻近邻居自由能量参数和碱基配对堆叠参数取值。克服了半扩展结构中对假结的表示模型存在参数精度低、自由能量取值不准确，计算方法误差大等缺陷，使得搜索速度、正确率、敏感性和特异性相较于现有技术有明显提高，预测正确率达到93.7％，平均敏感性达到98.2％，平均特异性达到97.5％。在平面假结和非平面假结的预测上比现有技术更有效。

附图说明

图1是根据本发明的包含假结基于扩展结构的RNA折叠结构的预测方法的流程图。

图2是本发明查找连续堆叠与扩展结构的流程图；

图3是根据本发明预测装置中处理单元的流程图；

图4是RNA折叠结构实例示意图；

图5是本发明RNA折叠结构改进能量参数与计算方法的例子；

图6是本发明包含假结的RNA中改进优化后W(i,j))与V(i,j最小自由能量的模型表示；

图7是本发明包含假结的RNA扩展结构的局部表示示意图。

具体实施方式

首先说明关于RNA序列、碱基对、假结等的概念。

RNA序列：RNA分子侧链上四种碱基的排列顺序，一般用A、U、G、C表示碱基对：如果s_i·s_j∈{AU,CG,GU},则s_i·s_j构成碱基对。碱基对堆叠的能量为负值。假结：如果s_i·s_j∈{AU,CG,GU},s_k·s_l∈{AU,CG,GU},i<k<j<l,则基对s_i·s_j与s_k·s_l构成假结。

RNA一级结构：RNA序列侧链上四种碱基的排列顺序表示。一般来说RNA序列从5′到3′结束，这样整个序列s表示为s＝s₁s₂…s_n，s_i是RNA序列的第i个碱基，s_i∈{A,U,G,C}，RNA碱基子序列s_i,j是s的一个序列片段，表示为：s_i,j＝s_i…s_j。

RNA二级结构：RNA序列中的一组基对构成的集合构成RNA折叠结构，以S表示。对于任意基对，如果s_i·s_j∈S、s_i′·s_j′∈S且i＝i′，则j＝j′，亦即，一个基不可同时与两个及两个以上的基构成基对。基对与流离碱基可形成发卡环、堆叠、内环、外环、凸起等环结构。RNA三级结构：根据折叠动力学原理，RNA二级结构进一步折叠、扭曲形成的结构。

如图1，本发明的包含假结基于扩展结构RNA折叠结构的预测方法包括以下步骤：输入一段核糖核酸碱基序列；定义假结和扩展结构；建立包含假结基于扩展结构的核糖核酸假结结构数学表示模型；计算出模型的最小能量；根据最小自由能量原理，输出核糖核酸的折叠结构。

图2给出了本发明的连续堆叠处理：输入一段s＝s₁s₂…s_n序列，随机查找碱基，如果存在i、j，使得s_i和s_j配对，j-i≥3，并且s中存在三个以上连续的相邻基对s_i·s_j、s_(i+1)·s_k·s_l，则基对s_i·s_j和s_k·s_l封闭的区间确定为堆叠；对堆叠中所有配对的碱基进行标记；在堆叠封闭的游离碱基中继续查找配对的碱基，如果存在三个以上基对，确定为连续堆叠；如果存在两个以上连续堆叠的交叉，则构成假结。

图3给出了根据本发明中的扩展结构处理流程所对应预测装置的处理单元，包括核糖核酸输入单元，数据存贮单元，连续堆叠查找确定处理单元，扩展结构查找确定单元，包含假结的结构输出单元。

图4给出了RNA折叠结构对应的一级结构、二级结构、三级结构示意图，RNA在折叠过程中，其核糖核酸碱基序列可认为是一级结构，一级结构根据碱基配对规则，经过折叠形成包括内环、凸起、外环、发卡环等的二级结构，二级结构进一步折叠扭曲可形成三级结构。

定义1：RNA碱基序列S_i,j中，如果(i,j),(i+1,j-1),…，(k,l)都是基对并且无交叉配对，i<k<l<j，则由(i,j)和(k,l)∈S所封闭的结构称为堆叠，可表示为T₁[i,j]。若堆叠T₁[i,j]由(i,j)和(r,s)∈S所封闭，堆叠T₁[r’,s’]由(r’,s’)和(k,l)∈S所封闭，且碱基内部无交叉配对，i<r<r’<k<l<s’<s<j，v＝r’–r+s-s’>2，则由(i,j)和(k,l)∈S所封闭的RNA折叠结构称为2阶连续堆叠,可表示为T₂[i,j]。

同理，如果T₁[i,j]由(i,j)和(r,s)∈S所封闭，(k-1)阶连续堆叠由(r’,s’)和(k,l)∈S所封闭，i<r<r’<k<l<s’<s<j，v＝r’–r+s-s’>2，则由(i,j)和(k,l)∈S所封闭的结构，且碱基内部无交叉配对，称为k阶连续堆叠,表示为T_k[i,j]，T_k[i,j]的最小能量表示可为ET_k(i,j)，T_k[i,j]的长度可表示为LT_k(i,j)＝k-i+1或RT_k(i,j)＝j-l+1。设T₂[i,j]由两个嵌套的堆叠和其内部未配对碱基构成。设E₂(r,r’:s’,s)表示基对(r,s)和(r’,s’)构成的连续堆叠结构的能量，ET₁(i,j)表示基对(i,j))封闭的堆叠能量，ET₁(r’,s’)分别表示由基对(r’,s’)封闭的堆叠能量，则ET₂(i,j)＝ET₁(i,j)+E₂(r,r’:s’,s)+ET₁(r’,s’)+a(a是补偿参数)。同理ET_k(i,j)＝ET₁(i,j)+E₂(r,r’:s’,s)+ET_k-1(r’,s’)+b(b是补偿参数)。

设LT(i,j)∈{LT₁(i,j),LT₂(i,j)},ET(i,j)∈{ET₁(i,j),ET₂(i,j)}。在本发明的方法中,连续堆叠的自由能量和长度使用O(n³)的时间预处理并分别存于三角矩阵ES(i,j)、LS(i,j)中。

同理，由ET_k(i,j)的计算公式可知，计算连续堆叠的时间复杂度为O(n³)，空间复杂度为O(n²)。连续堆叠的计算可由动态规划算法实现。

定义2:一个扩展结构由满足条件的两个RNA碱基序列片断s_i,k和s_l,j构成，i<k<l<j。存在p和q，i<p<q<k，使s_p,q和s_l,j构成连续堆叠,且片段s_i,k内部碱基之间不存在配对，即：若存在m和n且m<n,若(m,n)是碱基对，则m<i或n>k,或m<i且n<i,或k>m且k>n,则片断s_i,k和s_l,j构成扩展结构。设P[i,k:l,j]表示其最优扩展结构，EP(i,k:l,j)表示P[i,k:l,j]的最小能量，相应地，LP(i,k:l,j)＝j-l+1或LP(i,k:l,j)＝k-i+1表示P[i,k:l,j]的长度。一旦扩展结构P[i,k:l,j]确定，LP(i,k:l,j)也唯一确定。LP(i,k:l,j)可使用O(n³)空间存储P[i,k:l,j]；同样地，LP(i,k:l,j)可使用O(n³)空间存储P[i,k:l,j]。

图5表示在RNA折叠过程中，给出的包含12个碱基的RNA序列，根据碱基配对规则和堆叠参数，计算该碱基序列能量的实例。

RNA折叠结构中，针对k阶连续堆叠和扩展结构，其对应的程序计算如下：

在RNA结构中，计算k阶连续堆叠和扩展结构能量和长度

//注：设(i,j)表示RNA碱基s_i和s_j构成的基对，g表示RNA折叠结构中k阶连续堆叠的补偿系数。P’表示扩展结构中假结的一个基对的补偿值，Q’表示扩展结构中假结一个未配对碱基的惩罚值。//

Algorithm(S,k)

1.

2.

3.For r＝4to n

4.For i＝1to n-r

5.j←i+r+2；

6.If(i,j)&(i+1,j-1)

7.{LS₁(i,j)＝1；k←i；l←j；

//改进计算k阶连续堆叠和扩展结构的能量及长度的计算方法

8.ES₁(i,j)←ES₁(i,j)+g*E₁(k,k+1:l-1,l)+g*E₂(k,k+1:l-1,l)

+g*E₂(k+1,k+2:l-2,l-1)；

9.While(k,l)&(k+1,l-1)&(k+2,l-2)((l-k)>4)

10.ES_i(i,j)←E_iS_i(i,j)+g*E_i+1(k,k+1:l-1,l)+g*E_i+1(k+1,k+2:l-2,l-1)；

11.LS_i(i,j)++；k++；l--；

Loop

12.ES_i(i,j)←ES_i(i,j)+P’；

//改进RNA结构中k阶连续堆叠和扩展结构的能量与长度的计算方法

13.If(k＝i+2&l＝j-2)

14.While k＝i to i+U+1

15.for l＝j-U-1+k-i to j

16.If(k,l)

17.V←ES_i(i,j)+g*E_i+1(i,k:l,j)+ES_i(k,l)+(k-i+j-l-2)*Q’-1；

18.W←g*E_i+1(i,k:l,j)+ES_i(k,l)+(k-i+j-l-2)*Q’+2

19.If(V<ES_i+1(i,j)&W<ES_i+1(i,j))

20.ES_i+1(i,j)←V；

21.LS_i+1(i,j)←LS_i(i,j)+LS_i(k,l)；

Loop

22.End while

RNA折叠结构可分解为由一个扩展结构和一个子序列，或两个交叉的扩展结构和一个子序列。一个扩展结构又可以分解为k阶连续堆叠和多分枝环，这样的话，假结可以递归地表示。扩展结构本身也可包含假结，两个扩展结构的交叉又构成假结结构，这样扩展后的预测方法可以包含交叉假结。

引入扩展结构和k阶连续堆叠模型，利用k阶连续堆叠计算扩展结构，使用扩展结构的交叉计算嵌套和非嵌套的假结结构，建立新的RNA折叠结构数学表示模型。基于新的包含假结的折叠结构数学表示模型，设计和实现动态规划算法，预测包含任意平面和非平面假结的RNA折叠结构。

然而，利用经典的PknotsRG算法不能预测交叉假结，但基于半扩展结构的预测方法及装置也存在假结结构表示模型缺陷，自由能量参数缺陷，没有优化等问题。本发明可利用扩展的PknotsRG算法来预测任意的平面假结和非平面假结。由一个扩展结构和一个子序列构成假结结构的计算，或两个扩展结构和一个子序列的假结结构的计算增加到MFOLD计算模型中构成假结计算模型，图2和图3给出基本模型的图解表示。

图6表示在RNA折叠过程中，根据扩展结构和最小自由能量原理，对W(i,j)和V(i,j)改进后的部分示意图，其定义及计算过程如下所述。

图7是包含假结的基于扩展结构的RNA折叠结构部分示意图，共可包含至少8个情况的结构示意图。在计算过程中会包含各种情况的计算筛选优化。

给定一个序列s＝s₁s₂…s_n，序列片段s_i,j＝s_i…s_j，1＜i＜j＜n。设W(i,j)是在s_i和s_j不构成基对(i,j)的情况下，子序列s_i,j对应的包含假结的RNA折叠结构S的最小能量。设V(i,j)是s_i和s_j构成基对(i,j)的情况下，子序列s_i,j对应的包含假结的RNA折叠结构S的最小能量。

下面给出数学模型中W(i,j)和V(i,j)的计算公式。

V(i,j)由下列三种情况计算:S是堆叠，S是2阶连续堆叠，S是k阶连续堆叠(k 3)，i<k<j。

设E_k(i,j)是由基对(i,j)S所封闭的k阶连续堆叠的最小能量。如果(i,j)，(k,l)S，1≤i<k<l<j≤n,设(i,k:l,j)是以(i,j)和(k,l)为封闭基对的2阶连续堆叠，其能量为E₂(i,k:l,j)。

在扩展结构改进参数及自由能量计算中，本发明使用未配对碱基数目u和基对数目k为变量的函数来表示：E_k＝B+kM+uP。其中B表示构成一个扩展结构的补偿值，M表示扩展结构中每一基对的补偿值，P表示扩展结构中每一个未配对碱基的补偿值。

1)W(i,j)＝V(i,j)＝+∞，若j-i<4

2)V(i,j)＝+∞,若碱基i与j不构成基对

3)W(i,i)＝0,碱基i本身不能与自己配对

4)

使用动态规划算法,从RNA碱基序列第3个核苷酸序列开始计算，

计算所有的3核苷酸的最小自由能量，以此类推，直至计算W(1,n)。如果碱基j-i＝d≥3,则V(i,j)、W(i,j)借助于碱基i’和j’(j’-i’<d)来计算。

本发明的方法与PKNOTS算法、半扩展结构方法的加以实验比较，用VC++编程实现本发明的方法，并与PKNOTS算法进行比较。在此基础上，优化能量参数，对PseudoBase数据库和Rfam数据库的所有序列进行计算。Pknots算法和LP算法只能预测部分平面假结，PKNOTS算法是目前预测任意平面假结和部分非平面假结的最好算法。因此本发明的方法的测试结果主要与PKNOTS算法和半扩展结构方法进行比较。首先对PKNOTS算法和半扩展结构方法测试集合进行计算，使用的能量参数与PKNOTS算法、半扩展结构方法相同，但精确定义了扩展结构，引入基于扩展结构的同轴堆叠，包括包含假结基于扩展结构的同轴堆叠，使本发明的方法有利于形成准确完整的RNA折叠结构，包括连续堆叠，环结构和假结结构。克服了半扩展结构中对假结的表示模型存在参数精度低、自由能量取值不准确，计算方法误差大等缺陷，改进了如上所述的计算方法，其计算结果如下。

说明：按照本领域常规知识，计算机的计算时间一般由CPU主频、主板结构、内存大小协同配合有关。计算时间的改进主要由在计算机配置相同的情况下由计算方法(算法)的改进获得。

表1本发明的方法与半扩展结构算法、PKNOTS算法的计算时间比较

表2本发明的方法与PKNOTS算法的不同结果的比较

表3 CN104765983A公开的半扩展方法与PKNOTS算法不同结果的比较

表4本发明方法与CN104765983A公开的半扩展方法不同结果的比较

本发明的方法和PKNOTS算法的计算时间的比较见表1。本发明的方法使用内存为4MB的PC机进行测试，PKNOTS算法使用内存为4GB的高性能计算机Silicon GraphicsOrigin200进行测试。从表1可知，计算长度为75个碱基的RNA序列，本发明的方法使用21秒，而PKNOTS算法使用20分钟。计算长度为105个碱基的RNA序列，本发明的方法使用97秒，而PKNOTS算法使用235分钟。计算长度为200个碱基的RNA序列，本发明的方法使用26分钟，而PKNOTS算法不能计算。事实上，本发明的方法可以成功预测长度为1000个以上碱基的RNA序列的折叠结构。

由于本发明的方法基于扩展结构进行计算，并且引入更多的同轴堆叠，特别是假结的同轴堆叠，使本发明的方法有利于形成完整的茎区和正确的假结结构。

在使用相同的能量参数下，表2表明是本发明与PKNOTS算法不同结果的比较，不同的15个序列的敏感性和特异性的比较结果，本发明的方法的平均敏感性为98.2％，好于PKNOTS算法的71.7％；本发明的方法的平均特异性为97.5％，好于PKNOTS算法的70.6％，有显著改进。表3表明是半扩展方法与PKNOTS算法的不同结果的比较，针对不同的15个RNA序列的敏感性和特异性的比较结果，半扩展方法的平均敏感性为88.1％，好于PKNOTS算法的71.7％；本发明的方法的平均特异性为86.3％，好于PKNOTS算法的70.6％。

表4表明是本发明与半扩展方法不同结果的比较，针对不同的15个RNA序列的敏感性和特异性的比较结果，本发明的方法的平均敏感性为98.2％，好于半扩展方法的88.1％％；本发明的方法的平均特异性为97.5％，好于半扩展方法的86.3％，有显著改进。

因此测试结果表明，本发明的方法的搜索速度、平均敏感性和平均特异性都明显好于现有技术半扩展方法与PKNOTS算法。

PseudoBase国际RNA数据库的测试结果。

PseudoBase是一个RNA假结数据库。本发明的方法测试了PseudoBase数据库的全部245个序列和Rfam14.1数据库的部分序列，预测了381个序列包含假结，预测正确假结的序列为357个，正确率为93.7％；

引入扩展结构和k阶连续堆叠建立新的RNA假结数学表示模型。基于该模型提出一个时间复杂度为O(n³)和空间复杂度为O(n²)的动态规划方法，预测包含任意平面假结和较复杂的非平面假结的RNA折叠结构。

PKNOTS算法使用时间复杂度为O(n⁶)和空间复杂度为O(n⁴)，时空复杂度偏高，计算包含平面假结和部分非平面假结的折叠结构，计算的假结由不超过两个缺口结构表示。本发明的方法使用时间复杂度为O(n³)和空间复杂度为O(n³)计算假结，时空复杂度比PKNOTS算法有明显改进。假结可由不超过两个扩展结构表示，计算的RNA序列长度可超过1600个碱基。从测试结果可知，本发明的方法的搜索速度、正确率、敏感性和特异性都比半扩展方法与PKNOTS算法好。因此本发明的方法在平面假结与非平面假结的预测上比半扩展方法与PKNOTS算法更有效。

本发明的方法可计算由堆叠、发卡还、内环、凸起和多分枝环等子结构构成的RNA折叠嵌套假结和交叉假结结构。

虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本发明而采用的实施方式，并非用以限定本发明。任何本发明所属技术领域内的技术人员，在不脱离本发明所揭露的精神和范围的前提下，可以在实施的形式上及细节上作任何的修改与变化，但本发明的专利保护范围，仍须以所附的权利要求书所界定的范围为准。