RNA二级结构预测算法的研究进展

摘 要：在简要介绍了RNA的基础知识之后，对RNA二级结构的定义、表示方法、数据库等内容进行了详细阐述，并重点探讨了RNA二级结构预测方法的原理、适用范围及优缺点。目前，传统的RNA二级结构预测方法有比较序列分析法和最小自由能算法；新进发展的算法有支持向量机算法、基于堆积协变信息与最小自由能算法、基于局部茎搜索的算法、基于快速动态权重匹配算法、免疫粒子群算法、基于茎区的自由能算法、质心法。经过预测精度、复杂度、预测假节能力的对比，发现基于堆积协变信息与最小自由能算法和基于快速动态权重匹配算法，预测结果比较理想。

关键词：RNA；RNA二级结构预测；算法；综述

中图分类号：Q74 文献标识码：A 文章编号：1006-060X（2014）18-0003-06

Review of RNA Secondary Structure Prediction Algorithms

HUANG Yi-zi，LI Du-yue，LIU Wei，ZHOU Wei

（Hunan Engineering and Technology Research Center for Biopesticide and Formulation Processing，

Hunan Key Laboratory for Biology and Control of Plant Diseases and Insect Pests， College of Plant

Protection， Hunan Agricultural University， Changsha 410128， PRC）

Abstract：With RNA was found to have important biological functions， RNA research has gradually become a hotspot. Phylogenetic Methods and Minimum Free Energy algorithm has been widely used to predict RNA secondary structure. because of the limitations of the two algorithms， there has emerged many new algorithms .This paper gives a review of the current research progress about RNA secondary structure， including the RNA secondary structure， representing methods of RNA secondary structure， databases of RNA secondary structure， the traditionally and recently new developed RNA prediction algorithms as well as the advantages and disadvantages of the said algorithms. Support Vector Mechanism、Covariance with Stacking and Minimum Free Energy、StemFind、Fast Searching of Max Dynamic Weight Stem、algorithm based on immune partial swarm optimization ensemble、algorithm-helix-based dynamic programming and Centroid are mainly introduced in this paper. After comparison of precision， complexity and capability of predicting knots， Covariance with Stacking based on Minimum Free Energy and Fast Searching of Max Dynamic Weight Stem are ideal combination algorithms.

Key words：RNA； RNA secondary structure prediction； algorithm； review

1 RNA的基础知识

1.1 RNA的定义

核糖核酸（RNA）是由核糖核苷酸在3′端与5′端的磷酸二酯键的缩合作用下形成的一类链状分子。RNA链状分子的基本组成单位是核苷酸，一分子的核苷酸则是由磷酸、含氮碱基和核糖分别一个分子组成，四种碱基及其分子结构见图1 [1]。

RNA与脱氧核糖核酸（DNA）不同之处在于：组成DNA的单体的五碳糖为脱氧核糖，而组成RNA的是核糖；组成DNA的四种碱基中有一种胸腺嘧啶T，而RNA中的是尿嘧啶U。RNA序列长度不一，短的只有21～23 bp，如microRNA，长的达1 000 bp以上[2]。在生物中心法则中，RNA是基础信息媒介，作为遗传信息传递的中间媒介[3]。

1.2 RNA的结构

碱基堆积所需能量不同导致了RNA分子构型和种类的多样性，以适应其在细胞中各种功能。RNA分子的结构一般分为三个层次：一级结构、二级结构和三级结构。一级结构是RNA的序列信息，是指由A、U、G、C四种核糖核苷酸按照特定的顺序特征组成的字符串[4]。RNA 的二级结构是指 RNA 分子在自然条件下盘绕、卷曲，借助碱基间的氢键相互连接所形成的部分碱基配对（茎）与单链（环）交替出现的茎环结构[5]。对RNA功能起着决定性作用的是RNA的三级结构，三级结构是在二级结构的基础之上，结构中的各个元素之间相互作用，形成的三维立体结构，如图2所示。RNA 二级结构是 RNA 研究领域的重点和难点，对 RNA 三级结构的预测很大程度上取决于二级结构预测的结果。

1.3 RNA的种类和功能

细胞质中参与蛋白质合成的主要有3类RNA：核糖体的主要组成成分核糖体RNA（Ribosomal RNA，rRNA）、运输氨基酸的到核糖体上的转运RNA（Transfer RNA，tRNA）和蛋白质合成模板的信使RNA（Messenger RNA，mRNA）。它们在细胞RNA中所占总量的比例相差较大，分别为85%、12%和2%左右。这3种RNA由于各自的功能不同还可再细分，且种类数量差别较大，其中rRNA有3～4种，tRNA超过50种，而mRNA多达1 000种以上。除上述3种主要的RNA以外，还有一些特殊的RNA，例如核不均一RNA（hnRNA）、小核RNA（Small Nuclear RNA，snRNA）、胞质小分子RNA（scRNA）、

MicroRNA（miRNA）、小干扰RNA（Small Interfering RNA，siRNA）等[6]。其中，snRNA主要参与hnRNA的剪切、转运；hnRNA是成熟mRNA的前体；scRNA是蛋白质在内质网定位合成的信号识别颗粒的组成成分；

miRNA在基因沉默现象和RNA干扰（RNAi）技术中发挥重要作用；siRNA和miRNA一起寻找特定的 mRNA，

并使它们甲基化，从而影响某些特定基因的表达[7]。

2 RNA的二级结构

2.1 定 义

RNA的二级结构包括6种元素：双链螺旋区

（Duplex）、单链区（Single Stranded Region）、发夹（Hairpin Loop）、膨胀环（Bulge）、内环（Internal Loop）和多分支环（Junction）[8]。

假结是RNA二级结构中的一种特殊的复杂元素，在真实结构中有些RNA没有假结，有些RNA拥有大量的假结，更多的RNA只存在少量假结[9]。假结的存在对RNA分子的功能起着决定性的作用，例如在核糖体中，rRNA中存在着一个连接了三个元素的假结，如果该假结被降解，核糖体就会丧失其生物活性，不会参与到蛋白质的合成过程中。目前，还无法从序列层面上判断一种RNA到底会存在多少假结，但是假结一旦预测错误，将会连锁地引起正常茎区的预测错误，因此正确地预测假结是RNA二级结构预测中最富挑战性的环节，能否精度地预测假结是评价RNA二级结构预测算法优劣非常重要的指标。

2.2 表示方法

用于表示RNA二级结构的图形有很多种，例如多边形图或曲线图、括号图、圆顶图、圆圈图、山峰图，以及表示所有可能螺旋区的点阵图等，见图3。

2.3 数据库及分类

从简单的一级结构，到二级结构，再到复杂的三级结构乃至四维晶体结构，人们对RNA结构的了解越来越深入，累积了的大量成熟的理论和研究成果。随着全球网络化的发展，这些基础数据资源大部分得以共享，为RNA的进一步研究提供了更广阔的空间。表1中列出了当前常用的RNA数据库资源的网址。

3 RNA二级结构的预测方法

尽管目前已获得大量的RNA一级结构信息，但高级结构的信息资源还有限，但是x射线晶体衍射和核磁共振法等常规的三维结构测定方法，不仅花费较大，而且不是对所有大分子都有效，并不适合推广使用。因此结合对已有分子结构和功能的认识，采取生物信息学手段，通过计算机模拟来获得大部分生物分子的结构信息是目前较常用的大分子三维结构测定方法。

3.1 传统方法

RNA二级结构的预测算法研究已经有30 a以上的历史，从所依据的生物学原理可分为比较序列分析法（Phylogenetic Methods）和最小自由能算法两大类。前者要求必须有一组具有较高序列相似性的RNA序列作为比对的模板[10]；后者的原理则是假设RNA的自然二级结构是稳定的，根据热力学理论，物体在稳定状态时其自由能是最小的，对RNA序列给定含有自由能参数的热力学模型可求得自由能最小的二级结构[11]。

3.1.1 比较序列分析法 比较序列分析法是对多条序列进行互补碱基的共变联配（Covariant-alignment），需要提供已知RNA序列的数据库作为依据，查找与需要预测的RNA序列的高近似度序列，以一定的相关数学模型为依托共同研究推算所给RNA序列的二级结构，有共变模型（Covariance Model，CM）和随机上下文无关文法模型（Stochastic Context-free Grammars Model，SCFG）两种常用算法。共变模型是由隐马氏模型

（Hidden Markov Models，HMMs）发展而来，在模型中对序列各分子进行相互比较，逐步测算出最优结构的形成概率，再通过联配、模型训练和模型参数的修正3个步骤来完成预测。随机上下文无关文法模型是把RNA序列看成是具有一定语法规则的语句，通过这些语法规则来分析RNA序列中存在的碱基配对关系，也就是它的语义，从而得到该序列的二级结构[12]。比较序列分析法是预测RNA二级结构最精确的方法，可以预测假结，但是要以大量的同源序列数据为前提。如果序列长度过长，且同源序列信息又较少或没有，则很难进行预测。

3.1.2 最小自由能算法 基于最小自由能的RNA二级结构预测算法主要有基于矩阵的动态规划算法和基于启发式规则的随机（局部）搜索算法两类。动态规划算法的基本思想是将求解长序列二级结构的自由能转化为求若干个短序列二级结构自由能的情形，再根据递归算法来寻找最小自由能路径；即，将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解[13]，该算法的优点是对特定的序列可以求出最优解。基于启发式规则的随机搜索算法是通过引入一些启发式规则，在RNA二级结构的解空间中进行局部搜索，直到满足一定的终止条件为止。最小自由能算法，对于小分子RNA的二级结构预测更加有效，然而当面对长序列RNA分子时，准确度会大打折扣；且该方法很少关注假结，其发展空间较大。

3.2 新方法

由于传统的预测方法存在算法复杂度大或者无法预测分子量大的RNA序列等局限，而且很多算法都未考虑假结的情况，因此近年来在传统方法的基础上，发展了一些新算法[14]。

3.2.1 支持向量机法 支持向量机（Support Vector Mechanism，SVM）是建立在统计学习理论和结构风险最小原理基础上，根据有限样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的推广能力。统计学习理论可绕过RNA分子序列中基本结构的物理和化学分析过程，直接从结果对RNA结构进行统计分析；同时，还可克服传统统计学理论对先验信息要求过多限制，在利用观测数据对依赖关系进行估计时，只需知道未知依赖关系所属函数集的某些一般性质[15]。与神经网络类似，SVM模型将训练样本RNA进行编码作为输入，而对应的二级结构类别作为样本输出。学习完毕后，将需要预测的序列采用相同编码方式输入，经过SVM模型计算可得到一个序列，通过恢复操作即可得到该序列对应的二级结构。SVM的优点主要有：适合小样本；非线性模型，其结果更加可靠；避免了维数灾难；避免过拟合；具有泛化推广能力。其缺点主要有：无显性表达式；建模时核函数的选择需基于经验；但处理大样本时速度慢。

3.2.2 基于堆积协变信息与最小自由能算法 该算法是采用可靠的堆积协变信息计算模型，结合最小自由能算法，主要针对假结问题提出的RNA二级结构预测算法。该算法在协变量信息中引入碱基堆积，提高了协变信息评判的可靠性。重新定义堆积协变信息的计算公式简化为公式（1）。

B■■=■（1）

其中，B■■为N条同源i和j两个位点堆积协变信息的评估值，Bi-1，j+1、Bij和Bi+1，j+1分别为碱基对（i-1，j+1）、（i+1，j-1）的协变信息评估值，λ1、λ2分别为两个评估值的权重因子[16]。对该算法进行性能测试，发现当两个权重因子λ1和λ2的比值为5︰1时，预测性能达到最优。此方法最大的优势是能正确预测假结，其平均敏感性和特异性更突出，并且简化了堆积协变信息模型，使问题的复杂度大大降低。

3.2.3 基于局部茎搜索的预测算法 基于局部茎搜索的RNA二级结构预测算法也是针对RNA二级结构预测中假结问题而提出的基于茎区组合算法（StemFind）。该算法采用启发式搜索策略在茎的组合空间中搜索自由能最小并且频率最高的RNA二结构。StemFind把RNA的二级结构预测看成一个茎的组合的最优问题，采用自由能衡量候选茎的标准能作为评估对象，以逐步降低能量的方式来不断积累茎。该算法区别于以往基于茎的组合算法之处在于，它是通过启发式策略来选择合适的茎，以能量和茎的出现频率来评估候选解并生成最后的结构。这有利于RNA二级结构中假结的预测。StemFind具体的算法如下：选择候选茎时，把当前茎池中的所有茎按能量降序排名，能力强的茎为优，保留折叠初始阶段的“次优茎”，考虑范围随着茎的不断加入逐步减少，自由能逐步降低，RNA结构由高能态向低能态逐步转化，最后阶段选择最优茎。基于局部茎搜索的RNA二级结构预测算法在传统的最小自由能算法上加以创新，改善了最小自由能算法的缺点：即RNA折叠动力学因素使得RNA的二级结构并不总是处在能量最小的状态。因此，该方法在限制了算法复杂度的情况下能较高精度地预测RNA二级结构中的假结。

3.2.4 基于快速动态权重匹配的预测算法 基于快速动态权重匹配的RNA二级结构预测算法，是在最大动态权重茎区快速搜索（Fast Searching of Max Dynamic Weight Stem，FSMDWS）算法的基础上改进而来的，其原理是：对RNA序列进行自匹配，当序列长度大于最小发夹环的长度时，调用FSMDWS算法得到具有最大动态权重的茎区，对茎区长度进行检查，当长度小于最小茎区长度时认为匹配无效；得到有效的茎区后，对被有效茎区分开的子序列分别递归运行自匹配和各子序列之间相互匹配，得到双序列配对最大动态权的茎区时，对配对序列中被茎区分割开的子序列之间再次进行递归运行配对，如此递归直至序列长度无法形成茎区时终止[17]。该算法的时间复杂度低，扩充了假结搜索区域，能够预测更多RNA二级结构中可能出现的假结。

3.2.5 基于免疫粒子群集成的预测算法 基于免疫粒子集成的RNA二级结构预测算法是在粒子群算法（Particle Swarm Optimization，PSO）的基础上改进提出的。免疫PSO算法（以下简称IPSO）的原理是：如果PSO 算法在连续处理相对多的代数而最优个体没有提升到更优，这时就是陷入了局部最优，需要选取一定数量的个体替换生成的个体以跳出局部最优的缺陷。其原则是：选取适应值低和密度高的个体进行替换[18]。免疫集成算法（IPSOE）则是利用多个独立的IPSO并行搜索求解，其模型如图4所示。其中，IPSOi（i=1，2，…，N）是N个独立的粒子群优化算法，并行独立处理同一个优化问题，判断输出OPTIMAL是N个IPSO经过相同代数进化后得到的所有Pg中的最优结果。与传统的PSO相比，IPSOE的创新之处在于利用免疫机理，克服了传统PSO算法局部极值低的缺陷。

3.2.6 基于茎区组合的自由能算法 基于茎区组合的自由能算法是把RAN二级结构看成茎区的组合，结合自由能预测RNA二级结构，传统的最小自由能算法是以配对碱基为单位进行计算，而基于茎区的自由能算法是以茎区作为基本单位来划分计算的。算法过程如下：（1）对于给定的RNA序列，找出所有可能的茎区Hi，j，k，并用INN-HB（Individual Nearest Neighbor-Hydrogen Bond）能量模型计算茎的能量；（2）对于递归层中的任意一段RNA子序列Si，j，设Ei，j表示这段子序列所能形成的最优二级结构的自由能，Ei，j用动态规划算法按公式（2）计算（设定每个茎区环的长度至少为3，3对配对的碱基对，共至少8个碱基，当RNA长度小于8时，此时自由能为0）：（3）由于动态规划预测的结果都是嵌套结果，不能预测假结，根据自由能构造茎区树，根据自由能构造茎区树[19]。

Ei，j=min0（j-i<8）EHi，j，k，+Ei+k，j-kEi，j（i≤k

基于茎区的自由能算法在经典的最小自由能算法的基础提出基于茎区的动态规划计算方法，利用了最小自由能的优势，复杂度低，针对假结提出的茎区树方法，也有比较好的预测精确度。

3.2.7 质心法 质心法是受类别驱动的RNA二级结构预测方法，其不同于以往只用RNA一级结构信息预测RNA的二级结构，首次提出茎区的“质心”和“质心距”的概念，结合RNA已知的类别信息，根据已知的近似形状细化RNA的二级结构以提高预测的准确度。如果用三元组（i，j，k）表示某个RNA二级结构中的茎区（其中i表示距离5’端最近的开始位置，j表示距离 3’端最近的结束位置，k表示茎区长度），则质心可用二元组[（2i+k-1）/2，（2j-k+1）/2）]表示；对于分别来自不同同源序列的两个茎区（i，j，k+ 1）和（m，n，L + 1），设该组比对函数分别为 σ 和σ’ [20]，图5为质心距的计算和几何意义。

D函数主要用于衡量两个茎区H1和H2的差异：D（H1，H2）=dis（H1，H2）+λ×∣L1-L2∣；其中，dis（H1，H2）表示两个茎区的质心距，L1和L2表示两个茎区的长度，λ是调节权重的系数[20]。质心法在预测序列短和保守的RNA序列方面有良好的性能。利用D函数初始化的Hopfield网络来处理结构复杂的长序列RNA，可结合质心距和距离函数的思想，也可结合贪心思想和循环神经网络算法，对于处理RNA二级结构中的假结问题，能力更突出。

4 常用的RNA二级结构预测工具

RNA结构预测发展到现在，已经有了许多非常便利的预测工具。例如RNA Structure，这是一款经典的RNA二级结构预测软件，是在最小自由能原理的基础上利用Zuker算法来预测RNA二级结构，并对RNA序列进行折叠，操作简单。Mfold软件，是一款DNA和RNA都适用的结构预测在线软件。Vienna RNA Package是一款非常便利的RNA结构研究的免费软件包，适用于Unix平台，包含有许多结构预测算法和比较方法，比如RNAfold（用于预测具有最小自由能量的二级结构），RNAeval（用于估算RNA二级结构的能量值），RNAdistance（可比较RNA序列的二级结构），RNAsubopt（用于完善次优折叠的软件包）等，可对RNA二级结构进行预测与比较。

5 结 语

每一种RNA二级结构预测算法都有其自身的优势和缺陷，如果只用一种算法来进行预测，其结果的准确性和稳定性都有待考量，因此目前RNA二级结构预测领域的重点在于改进已有算法和模型，不断突破旧算法的局限性，将多种算法结合运用，尽可能地提高预测结果的准确性和稳定性。评价一个RNA二级结构预测算法的好坏要从以下3个方面进行考察：（1）算法的有效性和复杂度，预测结果的准确性需要保证到一定的水平，但复杂度（即在计算时间和存储空间的耗费）要有所控制；（2）能否预测假结，假结对RNA的二级结构非常重要；（3）能否充分利用已有的数据或先验信息，即在利用这些数据时，算法是否有着方便简易的可扩充性。

文章所述的新算法大多是在传统算法的基础上降低了复杂程度，并针对原算法或模型的局限性进行改进，把RNA二级结构中的假结预测考虑在内，大大提高了预测结果的准确性和可靠性，并且通过试验验证，能得到较优的预测结果，都是比较理想的RNA二级结构预测算法。

参考文献：

[1] 王魁伟. 基于能量优化的RNA二级结构预测[D]. 吉林：吉林大学硕士学位论文，2013.

[2] 张 骏. RNA二级结构预测的蛙跳算法及其并行化[D]. 福建：福建农林大学硕士学位论文，2012.

[3] 段学青. 基于图像处理的RNA二级结构比较算法[D]. 吉林：吉林大学硕士学位论文，2011.

[4] 杨 赫. RNA二级结构中假结的预测研究[D]. 吉林：吉林大学硕士学位论文，2013.

[5] 于 丹. RNA二级结构预测算法分析与比较[D]. 吉林：吉林大学硕士学位论文，2009.

[6] 董 浩. RNA二级结构预测方法研究[D]. 吉林：吉林大学博士学位论文，2012.

[7] 彭 政. 带假结的RNA二级结构预测算法研究[D]. 长沙：湖南大学硕士学位论文，2008.

[8] 刘次全，曹恩华，白春礼，等. 核酸结构多态性[M]. 北京：高等教育出版社，2000. 131

[9] 邹 权. RNA 二级结构预测方法综述[J]. 电子学报，2008，2（2）：331-337.

[10] 陈 翔. 基于局部茎搜索的RNA二级结构预测算法[J]. 生物化学与生物物理进展，2009，36（1）：115-121.

[11] 唐四薪. 基于词汇化随机文法模型的RNA二级结构预测[J]. 计算机工程与科学，2009，31（3）：128-131.

[12] 唐四薪. RNA二级结构预测的计算语言学方法[J]. 衡阳师范学院学报，2008，29（6）：90-92.

[13] 董军军. 动态规划算法和贪心算法的比较与分析[J]. 软件导刊，2008，17（2）：129-130.

[14] 方小永. 基于比较序列分析的RNA二级结构预测与评估[D]. 长沙：国防科技大学硕士学位论文，2007.

[15] Zhou W，Dai Z J，Chen Y，et al. High-dimensional descriptor selection and computational QSAR modeling for antitumor activity of ARC-111 analogues based on support vector regression（SVR）[J]. International Journal of Molecular Sciences，2012，13（1）：1161-1172.

[16] 杨金伟. 基于堆积协变信息与最小自由能预测含伪结的RNA二结构[J]. 生物工程学报，2008，24（4）：659-664.

[17] 骆嘉伟. 基于快速动态权重匹配的 RNA二级结构预测算法[J]. 计算机应用，2008，28（8）：2006-2009.

[18] 胡桂武. 基于免疫粒子群集成的RNA二级结构预测算法[J]. 计算机工程与应用，2007，43（3）：26-29.

[19] 夏培明. 基于茎区的自由能算法预测RNA二级结构[J]. 南京大学学报（自然科学版），2009，25（3-3）：139-141.

[20] 邹 权. 质心法：受类别驱动的RNA二级结构预测方法[J]. 南京大学学报（自然科学版），2009，45（5）：677-688.

（责任编辑：成 平）