基于改进的神经网络的RNA二级结构预测

林 航，李金铭

（福建农林大学，福建 福州 350002）

基于改进的神经网络的RNA二级结构预测

林 航，李金铭

（福建农林大学，福建 福州 350002）

在生物信息学中，存在一个热点问题为RNA二级结构预测，通过计算机仿真模拟和数学建模计算来“预测”这些结构信息具有较好的参考价值以及可信度，能够节省大量的时间与成本.本文提出了免疫算法与Hopfield神经网络算法相结合的IA-DHNN算法对RNA二级结构进行预测.算法采用相似距离函数、IA算法及k均值算法对神经元的初始值进行优化，提高了全局搜索能力，能简单、快速规范的获得最优解.仿真结果表明，本算法能够有效的对RNA二级结构进行预测，有较好的的预测效果.

RNA二级结构；免疫算法；Hopfield神经网络；预测

脱氧核糖核酸具有重要的生物学功能，是DNA到蛋白质间遗传信息的中间传递体[1].RNA二级结构是特定平面图，配对的部分构成局部的双螺旋结构，这就是RNA的二级结构[2]，它是一种平面的结构.

它的各种功能往往受到脱氧核糖核酸的结构的影响，因此脱氧核糖核酸的结构在一定程度上揭示着生命过程中RNA分子的作用，这些可以通过研究RNA的功能和结构间的关系.目前，使用实验方法在RNA信息数据的惊人的增长下，实现生物分子的具体的二级结构有着其自身的局限性，而且对所有分子并不是都有效的[3].

研究表明，对RNA二级结构预测，通过计算机仿真与数学建模的方法具有较高的可信度和参考价值，主要的类型有：

（1）动态规划的方法

动态规划方法是基于热力学原理.当RNA在一个稳定的环境，自由能最小，我们可以理解为RNA二级结构趋于稳定.最典型的是Zuker动态规划算法[4]，是自由能计算模型.该算法实现简单，但它不能预测带假结的RNA分子，由于其真实结构可能不是最低自由能，所以用这种方法来预测准确率低.

（2）比较序列法

比较序列的方法通常采用的是共变模型[5]和随机上下文无关语法模型[6].共变模型，首先通过小规模的比对，之后更大规模的子树和序列的比对概率被递归计算，直到得到最佳的比对.随机上下文是由一定的语法“句子”定义的规则，然后通过这些句子的分析，得到碱基配对关系的序列，从而使RNA二级结构得到预测[7].通过比较序列的方法可以预测RNA二级结构更好，更准确，但他们需要更多的同源序列，并且对同源序列还有一定的限制要求，花的时间也较多.

由于上述方法的局限性，组合优化算法被提了出来.通过使用这种方法，遗传算法[8-10]、模拟退火算法、Hopfield神经网络[11-12]等启发式算法被用来解决这类问题.本文提出了一种混沌Hopfield神经网络算法，将其应用于RNA二级结构的预测.

1 免疫算法

免疫算法(Immune Algorithm,IA)是一种进化算法，其灵感来自人体的免疫系统.该算法模拟人体免疫系统,是求解全局最优解的一种新的优化算法.记忆性和多样性机制，使免疫算法的具有良好的全局优化能力，很容易与其他方法结合，并得到很好的应用.免疫算法主要由以下几个部分构成：

抗原：免疫算法中，抗原对应目标函数和约束条件.

抗体：免疫算法中，抗体对应问题的解，可以随机产生一组解，也可以使用特定的方法赋予一个初始解.

免疫记忆：与抗原有最大亲和力的抗体加给记忆细胞.由于记忆细胞数量有限，新产生的与抗原亲和力较低的抗体将被替换为亲和力较高的抗体.在免疫算法中体现为较低亲和力的解被替换为较高亲和力的解.

免疫调节：高亲和力抗体和高密度抗体分别受到促进和抑制.在免疫算法中体现为在实施抗体的选择过程中通过计算抗体存活的期望繁殖率.

通过下图1可以清楚的看出免疫算法的一般步骤：

图1 免疫算法流程

2 Hopfield神经网络

Hopfield神经网络称为单层反馈网络因其是一个只有单一的神经元层次的结构，同时每个神经元与其他神经元的输出是相互连接的.0或者1是Hopfield神经网络的取值集合，yi(t+1)是神经元的输出，xi(t+1)是网络的输出，如公式(1)：

其中，Hopfield的输出值保持为0或1是通过激励函数实现的.

Hopfield神经网络在优化计算的应用中，目标函数有相应的能量函数，从而网络权值也被确定，当神经网络的能量达到最小时的解，就是问题的最优解.

3 免疫Hopfield神经网络（IA-DHNN）优化算法求解

3.1 RNA二级结构中的Hopfield神经网络

Hopfield神经网络用于RNA二级结构预测问题时，用基于最小自由能思想的茎区自由组合算法时，由于vi=0表示该神经元被选中，能量函数可以写成[13]：

其中，cij即为节点i和j间的权值，茎是否被选中决定了vi取0或1，ei表示茎i的能量；茎i与j是否相容来决定取值为0或1；非稳定茎和稳定茎间的相对率通过λ调整.

同时，第i个神经元的动力方程为：

其中，dij取值0表示边i和边j不相交，取值为1时表示边i和边j相交.h(x)作为激励函数，只有当x=0时，h(x)=1.茎区x环长度用distance(x)表示.公式(3)中分为惩罚项和激励项，惩罚项的权值参数A表示，激励项的权值用B表示.

3.2 IA-DHNN算法描述

对于Hopfield神经网络来说，其对初始值的依赖性很强，因此本文使用距离函数和免疫算法的多样性产生初始解，对神经网络的初始解进行优化，其中免疫算法通过产生若干代种群后，对其进行聚类，使用聚类中心作为DHNN神经元的初始输出，更新其初始解和输出值.其具体步骤如下：

（1）初始化，使目标函数和约束条件有相应的能量函数，问题的解为神经元的输出vi，令神经网络参数T=mmax，t=0；

（2）使用距离函数计算初始解，初始化神经网络；

（3）使用免疫算法产生80代抗体；

（4）采用K均值算法计算从免疫算法计算所得抗体的聚类中心；

（5）初始化神经网络，选取一个还未被访问的聚类中心，为该神经网络神经元的初始输出；

（6）当ui>0时，vi=1，否则vi=0.而vi=0说明该碱基配对；

（7）使用公式(4)中的定义的更新ui，vi；

（8）当满足终止条件，即满足ui(t+1)=ui(t)+Δui(t) Δt或者Δui(t)或者t=max，继续下一步,否则转(5)；

（9）计算当前解的目标函数值；

（10）当聚类中心全部被访问过,停止计算,否则转(4)；

（11）从中选取使目标函数值最小的解.

4 实验结果

4.1 评价标准

敏感性（X），特异性（Y）[14]和马休兹相互作用系数[15](MMC)是目前评价RNA二级结构准确率主要的3个度量参数.X和Y分别是指所有碱基对在真实结构中被正确预测到的比值和正确预测所有预测到的碱基对的比值.一般折中衡量上述两个参数的是MCC.

其中，TP是碱基对正确预测的个数；FN是碱基对在真实结构中存在，却没有被正确预测出的个数；FP是碱基对真实结构中不存在，但被错误预测到的个数；TN是不配对碱基被正确预测的个数.

4.2 参数设置和仿真结果比较

仿真中，A=0.1，B=0.2为神经网络的常量参数.最后得到实验结果见下表1.我们可以看出本文的算法优于其他算法.

表1 4种算法平均预测准确率的比较

5 结语

本文根据免疫算法多样性的有点，和神经网络对初值的依赖性，结合tRNA结构的保守性的特点，对神经网络的初值进行优化，将免疫神经网络混合算法首次运用于RNA二级结构预测，全局的搜索能力得到提高，使其不易陷入局部最优解，并获得一定的效果.

〔1〕林娟,钟一文,张骏.离散蛙跳算法预测RNA二级结构[J].南京师范大学学报(工程技术版),2011 (04).

〔2〕邢翀.RNA二级结构预测算法的研究[D].吉林大学,2012.

〔3〕林娟,钟一文.改进的免疫粒子群优化算法预测RNA二级结构[J].计算机工程与应用,2012(01).

〔4〕ZUKER M.On finding all suboptimal foldings of an RNA molecular [J].Science, 1989, 244 (4900):48-52.

〔5〕Ennysr.Durbar RNA Sequence Analysis using covariance models[J].Nucleic Acids Res.1994,22: 2079-2088.

〔6〕Sakakbara Y,Browm M,Hugheryr.Recent methods for RNA modeling using stochastic context-free grammars[C].Grochemorem.Gusfield D.Proceedings of the sikomar conference on combinatorial pattem matching Berlin:Springer-Verlag.1994,p:289-306.

〔7〕Cai L, Malmberg R.L, Wu Y.Stochastic modeling of RNA pseudoknotted structures: a grammatical approach [J].Bioinformatics.2003: 166-173.

〔8〕HU Yuh-Jyh.Prediction of consensus structural motifs in a family of coregulated RNA sequences [J].Nucleic Acids Research , 2002 , 30(7): 3886-3893.

〔9〕SHAPIRO B A , WU Jin-chu , BENGALI D , et al.The massively parallel genetic algorithm for RNA folding: MIMD implementation and population variation[J].Bioinformatics, 2001 ,17 (2): 137-148.

〔10〕WIESE K C , DESCHENES A A , HENDRIKS A G.Rna Predict-an evolutionary algorithm for RNA secondary structure prediction [J].IEEE/ ACM Transactions on Computational Biology and Bioinformatics, 2008 ,50): 25-41.

〔11〕T AKEFUJI Y ,CHEN Li-lin , LEE K c, et al.Parallel algorithms for finding a near-maximum independent set of a circle graph [J].IEEE Transaction on Neural Networks , 1990,1(3): 263-267.

〔12〕TAKEFUJI Y.LIN C W.LEE K C.A parallel algoriihm for estimating the secondary structure in ribonucleic acids [J].Biological Cybernetics ,1990,63(5):337-340.

〔13〕刘琦,张引,叶修梓,et al.基于离散Hopfield 网络求解极大独立集的茎区选择算法以及在RNA 二级结构预测中的应用[J].计算机学报，2008,31(1):51-58.

〔14〕GARDNER P P.GIEGERICH R.A comprehensive comparison of comparative RNA structure prediction approaches [J].BMC Bioinformatics.2004.5(1):1-40.

〔15〕BALDI p, BRUNAK S , CHA UVIN Y.et al.Assessing the accuracy of prediction algorithms for classification: an overview[J].Bioinformatics , 2000 , 6(5):412-424.

Q811

A

1673-260X（2014）03-0014-03