基于免疫与神经网络的 RNA 二级结构预测

第３４卷第７期　２　０　ｌ　４年７月　湖北科技学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｕｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｅ　Ｖｏ１．３４，Ｎｏ．７　Ｊｕ１．２０ｌ４　

文章编号：２０９５－４６５４（２０１４）０７—０００１—０２　

基于免疫与神经网络的ＲＮＡ二级结构预测　林航，李金铭　（福建农林大学，福建福州３５０００２）　摘要：ＲＮＡ二级结构预测是生物信息学领域的一个热点问题，通过计算机仿真模拟和数学建模计算来“预测”　这些结构信息，具有较好的参考价值以及可信度，并能够节省大量的时间与成本。本文通过改进传统的ＲＮＡ二　级结构预测算法，提出了混沌Ｈｏ　ｅｌｄ神经网络算法算法。算法以茎区作为神经元，同时采用相似距离函数、对　神经元的初始值进行优化，在获得初步结果后，通过使用混沌函数优化结果，使得其跳出局部最优解，提高了全局　搜索能力，能简单、快速规范的获得最优解。仿真结果表明，本算法能够有效的对ＲＮＡ二级结构进行预测，有较　好的的预测效果。　关键词：免疫算法；Ｈｏｐｆｉｅｌｄ神经网络；ＲＮＡ二级结构；预测　中图分类号：Ｑ８１１；ＴＰ３８９．１　文献标识码：Ａ　

脱氧核糖核酸具有重要的生物学功能，是ＤＮＡ到蛋白　质间遗传信息中间传递体”Ｊ。ＲＮＡ二级结构是特定平面　图，配对的部分构成局部的双螺旋结构，这就是ＲＮＡ的二　级结构　Ｊ，它是一种平面的结构。目前，使用实验方法在　ＲＮＡ信息数据的惊人的增长下，实现生物分子的具体的二　级结构有着其自身的局限性，而且对所有分子并不是都有　效的　引。　研究表明，对ＲＮＡ二级结构预测，通过计算机仿真与　数学建模的方法具有较高的可信度和参考价值，主要的类　型有：　（１）动态规划的方法　动态规划方法是基于热力学原理。Ｚｕｋｅｒ动态规划算　法为代表的　的动态规划算法，是自由能计算模型。该算　法实现简单，但它不能预测带假结的ＲＮＡ分子，由于其真　实结构可能不是最低自由能，所以用这种方法来预测准确　率低。　（２）比较序列法　比较序列的方法通常采用的是共变模型　和随机上下　文无关语法模型＿６　Ｊ。通过比较序列的方法可以预测ＲＮＡ　二级结构更好，更准确，但他们需要更多的同源序列，并且　对同源序列还有一定的限制要求，花的时间也较多。　由于上述方法的局限性，组合优化算法被提了出来。　通过使用这种方法，模拟退火算法、遗传算法　、Ｈｏ　ｅｌｄ　神经网络　”　等启发式算法被用来解决该问题。本文采　

用混沌Ｈｏｐｆｉｅｌｄ神经网络算法预测ＲＮＡ二级结构。　一、

混沌理论　

混沌是一种非线性现象，广泛存在于自然界中，它可能　看起来有些混乱，但其精致的结构，使随机性、遍历性和规　律性成为它的特点，某个范围内，其可以按自身的规律不重　复遍历所有状态。　・收稿日期：２０１４一ｏ３－２８　一般指的是通过随机确定性方程获得的随机性运动状　态，混沌状态变量被称为混沌变量。ｌｏｇｉｓｔｉｃ映射是是一个　常用的混沌系统，方程如下：　＋１＝／Ｊｚ　（１一　）　ｎ＝０，１，…ｎ　（１）　式（１）是一个动力学系统，肛作为其控制参数。　值确　定后，从任意的初值ｚ０　ｅ［０，１］，可以迭代得到一个确定的　时问序列Ｚｏ，ｚ　・・ｚ　。当　＝４时，是一个完全处于混沌　状态系统。混沌优化算法能够轻易的跳出局部最优解，归　功于它的混沌性。它的搜索机制表现很好，常常被用于算　法的混合中，并作了广泛研究。把混沌算子应用于遗传算　法中，提出了混沌遗传算法，取得了较好的效果。把混沌搜　索结合于微粒群算法，得到了混沌粒子群优化算法，都具有　很好的搜索性能。　二、Ｈｏｐｆｉｅｌｄ神经网络　Ｈｏｐｆｉｅｌｄ神经网络是一个只有单一的神经元层次的结　构，同时每个神经元与其他神经元的输出是相互连接的，称　之单层反馈网络。０或者１两种值是Ｈｏｐｆｉｅｌｄ神经网络的　取值集合。　（ｔ＋１）是神经元的输出，置（ｔ＋１）是网络的输　出，如公式（１）：　（ｔ＋１）＝　‘Ｉ）　ｘｊ（ｔ）一Ｑｉ　置（ｔ＋１）＝ｓ　（Ｙｊ（ｔ＋１），ｉ∈［１，ｎ］　（２）　ｓ　（ｘ）＝｛：姜　其中，Ｈｏｐｆｉｅｌｄ的输出值保持为０　或１是通过ｓｇｎ（ｘ）激励函数实现的。　Ｈｏｐｆｉｅｌｄ神经网络在优化计算的应用中，目标函数有相　应的能量函数，从而网络权值也被确定，当神经网络的能量　达到最小时的解，就是问题的最优解。　三、混沌Ｈｏｐｆｉｅｌｄ神经网络优化算法求解　１．应用于ＲＮＡ二级结构预测的Ｈｏｐｆｉｅｌｄ神经网络　２　湖北科技学院学报　第３４卷　Ｈｏｐｆｉｅｌｄ神经网络用于ＲＮＡ二级结构预测问题时，用基于　最小自由能思想的茎区自由组合算法时，由于　＝０表示　该神经元被选中，能量函数可以写成　：　Ｅ：耋ｅ　（１一ｖ　）＋　．耋耋Ｃｉ（１一Ｖｉ）（１一Ｖｊ）　

（３）　其中，Ｃ　即为节点ｉ和ｊ间的权值，茎是否被选中决定　了Ｖｉ取０或１，ｅ　表示茎ｉ的能量；茎ｉ与ｊ是否相容来决　定取值为０或１；非稳定茎和稳定茎间的相对率通过　调　整。　２．混沌Ｈｏｆｉｅｌｄ神经网络算法描述　对于Ｈｏｐｆｉｅｌｄ神经网络来说，其对初始值的依赖性很　强，因此本文使用距离函数产生初始解，对神经网络的初始　解进行优化。对Ｈｏｐｆｉｅｌｄ初步产生的最优解，通过使用混　沌函数对其值进行混沌化，使其跳出局部最优解，搜索全局　最优解，其具体步骤如下：　（１）定义问题，能量函数对应目标函数和约束条件，神　经元的输出Ｖ　对应问题的解，初始化神经网络参数，令Ｔ　＝ｍａｘ，ｔ＝０；　（２）使用距离函数计算初始解，初始化神经网络；　（３）初始化神经网络，选取一个还未被访问的聚类中　心，为该神经网络神经元的初始输出；　（４）当Ｕ　＞０时，Ｖ　＝１，否则Ｖ　＝０。而Ｖｉ＝０说明　该碱基配对；　（５）使用公式（４）中的定义的更新Ｕ　，Ｖ　；　（６）当满足终止条件，即满足Ｕ　（ｔ＋１）＝Ｕｉ（ｔ）＋ＡＵ　（ｔ）△ｔ或者△ｕ　（ｔ）或者ｔ＝ｍａｘ，继续下一步，否则转　４）；　（７）计算当前解的目标函数值；　（８）使用混沌函数对初步初始解进行混沌化，产生新　的初始值初始化神经网络；　（９）达到最大迭代次数，优化终止，从中选取使目标函　数值最小的解。　四、实验结果　１．评价标准　敏感性（ｘ），特异性（Ｙ）和马休兹相互作用系数　（ＭＭＣ）是目前评价ＲＮＡ二级结构准确率主要的３个度量　参数。Ｘ是所有碱基对在真实结构中被正确预测到的比　率。Ｙ是正确预测所有预测到的碱基对的比率。一般折中　衡量上述两个参数的是ＭＣＣ。　２．参数设置和仿真结果比较　仿真中，Ａ＝０．１，Ｂ＝０．２为神经挽留过的常量参数。　最后得到实验结果见下表１。我们可以看出本文的算法优　于其他算法。　表１　４种算法平均预测准确率的比较　五、结语　本文根据混沌算法的遍历性和随机性，和神经网络对　初值的依赖性，结合ＲＮＡ结构的保守性的特点，对神经网　络的初值进行优化，将Ｈｏｆｉｅｌｄ神经网络通过混沌函数进行　优化，首次运用于ＲＮＡ二级结构预测，提高了全局，搜索能　力，使其不易陷入局部最优解，并获得一定的效果。　参考文献：　［１］林娟，钟一文，张骏．离散蛙跳算法预测ＲＮＡ二级结　构［Ｊ］．南京师范大学学报（工程技术版），２０１１，（４）．　［２］邢种．ＲＮＡ二级结构预测算法的研究［Ｄ］．长春：吉林　大学。２０１２．　［３］林娟，钟一文．改进的免疫粒子群优化算法预测ＲＮＡ　二级结构［Ｊ］．计算机工程与应用，２０１２，（１）．　［４］ＺＵＫＥＲ　Ｍ．Ｏｎ　ｆｍｄｉｎｇ　ａｌｌ　ｓｕｂｏｐｔｉｍａｌ　ｆｏｌｄｉｎｇｓ　ｏｆ　ａｌｌ　ＲＮＡ　ｍｏｌｅｃｕｌａｒ［Ｊ］．Ｓｃｉｅｎｃｅ，１９８９，２４４（４９００）：４８～５２．　［５］Ｅｎｎｙｓｒ．Ｄｕｒｂａｒ　ＲＮＡ　Ｓｅｑｕｅｎｃｅ　Ａｎａｌｙｓｉｓ　ｕｓｉｎｇ　ｃｏｖａｒｉａｎｃｅ　ｍｏｄｅｌｓ［Ｊ］．Ｎｕｃｌｅｉｃ　Ａｃｉｄｓ　Ｒｅｓ．１９９４，（２２）：２０７９～２０８８．　［６］Ｓａｋａｋｂａｒａ　Ｙ，Ｂｒｏｗｍ　Ｍ，Ｈｕｓｈｅｒｙｒ．Ｒｅｃｅｎｔ　ｍｅｔｈｏｄｓ　ｆｏｒ　ＲＮＡ　ｍｏｄｅｌｉｎｇ　ｕｓｉｎｇ　ｓｔｏｃｈａｓｔｉｃ　ｃｏｎｔｅｘｔ—ｆｒｅｅ　ｇｒａｍ／ｎａｒｓ　［Ｃ］．Ｇｒｏｃｈｅｍｏｒｅｍ．Ｇｕｓｆｉｅｌｄ　Ｄ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｓｉｋｏｍａｒ　ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｐａｔｔｅｍ　ｍａｔｃｈｉｎｇ　Ｂｅｒ－　ｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ．１９９４：２８９～３０６．　［７］Ｃａｉ　Ｌ，Ｍａｌｍｂｅｒｇ　Ｒ．Ｌ，Ｗｕ　Ｙ．Ｓｔｏｃｈａｓｔｉｃ　ｍｏｄｅｌｉｎｇ　ｏｆ　ＲＮＡ　ｐｓｅｕｄｏｋｎｏｔｔｅｄ　ｓｔｒｕｃｔｕｒｅｓ：ａ　ｇｒａｍｍａｔｉｃａｌ　ａｐｐｒｏａｃｈ　［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ．２００３：１６６～１７３．　［８］ＨＵ　Ｙｕｈ—Ｊｙｈ．Ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｃｏｎｓｅｎｓｕｓ　ｓｔｒｕｃｔｕｒａｌ　ｍｏｔｉｆｓ　ｉｎ　ａ　ｆａｍｉｌｙ　ｏｆ　ｃｏｒｅｇｕｌａｔｅｄ　ＲＮＡ　ｓｅｑｕｅｎｃｅｓ【Ｊ］．Ｎｕｃｌｅｉｃ　Ａｃｉｄｓ　Ｒｅｓｅａｒｃｈ，２００２，３０（７）：３８８６～３８９３．　Ｉ　９　Ｉ　ＳＨＡＰＩＲＯ　Ｂ　Ａ，ＷＵ　Ｊｉｎ—ｃｈｕ，ＢＥＮＧＡＬＩ　Ｄ，ｅｔ　ａ１．　Ｔｈｅ　ｍａｓｓｉｖｅｌｙ　ｐａｒａｌｌｅｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ＲＮＡ　ｆｏｌｄｉｎｇ：　ＭＩＭＤ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ａｎｄ　ｐｏｐｕｌａｔｉｏｎ　ｖａｒｉａｔｉｏｎ［Ｊ］．　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００１，１７（２）：１３７～１４８．　［１０］ＷＩＥＳＥ　Ｋ　Ｃ，ＤＥＳＣＨＥＮＥＳ　Ａ　Ａ，ＨＥＮＤＲＩＫＳ　Ａ　Ｇ．　Ｒｎａ　Ｐｒｅｄｉｃｔ—・ａｌｌ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ＲＮＡ　ｓｅｃｏｎｄａ－・　ｒｙ　ｓｔｒｕｃｔｕｒｅ　ｐｒｅｄｉｃｔｉｏｎ［Ｊ］．ＩＥＥＥ／ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｂｉｏｌｏｇｙ　ａｎｄ　Ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２００８，（５０）：　２５～４１．　［１１］Ｔ　ＡＫＥＦＵＪＩ　Ｙ，ＣＨＥＮ　Ｌｉ—ｌｉｎ，ＬＥＥ　Ｋ　ｅ，ｅｔ　ａ１．Ｐａｒａｌ—　ｌｅｌ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｆｉｎｄｉｎｇ　ａ　ｎｅａｒ—ｍａｘｉｍｕｍ　ｉｎｄｅｐｅｎｄｅｎｔ　￥ｅｔ　ｏｆ　ａ　ｃｉｒｃｌｅ　ｇｒａｐｈ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔ—　ｗｏｒｋｓ，１９９０，１（３）：２６３～２６７．　［１２］刘琦，张引，叶修梓．基于离散Ｈｏｐｆｉｅｌｄ网络求解极大　独立集的茎区选择算法以及在ＲＮＡ二级结构预测中　的应用［Ｊ］．计算机学报，２００８，３１（１）：５ｌ～５８．