林 航，李金銘

（福建農(nóng)林大學(xué)，福建 福州 350002）

基于改進(jìn)的神經(jīng)網(wǎng)絡(luò)的RNA二級結(jié)構(gòu)預(yù)測

林 航，李金銘

（福建農(nóng)林大學(xué)，福建 福州 350002）

在生物信息學(xué)中，存在一個熱點(diǎn)問題為RNA二級結(jié)構(gòu)預(yù)測，通過計算機(jī)仿真模擬和數(shù)學(xué)建模計算來“預(yù)測”這些結(jié)構(gòu)信息具有較好的參考價值以及可信度，能夠節(jié)省大量的時間與成本.本文提出了免疫算法與Hopfield神經(jīng)網(wǎng)絡(luò)算法相結(jié)合的IA-DHNN算法對RNA二級結(jié)構(gòu)進(jìn)行預(yù)測.算法采用相似距離函數(shù)、IA算法及k均值算法對神經(jīng)元的初始值進(jìn)行優(yōu)化，提高了全局搜索能力，能簡單、快速規(guī)范的獲得最優(yōu)解.仿真結(jié)果表明，本算法能夠有效的對RNA二級結(jié)構(gòu)進(jìn)行預(yù)測，有較好的的預(yù)測效果.

RNA二級結(jié)構(gòu)；免疫算法；Hopfield神經(jīng)網(wǎng)絡(luò)；預(yù)測

脫氧核糖核酸具有重要的生物學(xué)功能，是DNA到蛋白質(zhì)間遺傳信息的中間傳遞體[1].RNA二級結(jié)構(gòu)是特定平面圖，配對的部分構(gòu)成局部的雙螺旋結(jié)構(gòu)，這就是RNA的二級結(jié)構(gòu)[2]，它是一種平面的結(jié)構(gòu).

它的各種功能往往受到脫氧核糖核酸的結(jié)構(gòu)的影響，因此脫氧核糖核酸的結(jié)構(gòu)在一定程度上揭示著生命過程中RNA分子的作用，這些可以通過研究RNA的功能和結(jié)構(gòu)間的關(guān)系.目前，使用實(shí)驗(yàn)方法在RNA信息數(shù)據(jù)的驚人的增長下，實(shí)現(xiàn)生物分子的具體的二級結(jié)構(gòu)有著其自身的局限性，而且對所有分子并不是都有效的[3].

研究表明，對RNA二級結(jié)構(gòu)預(yù)測，通過計算機(jī)仿真與數(shù)學(xué)建模的方法具有較高的可信度和參考價值，主要的類型有：

（1）動態(tài)規(guī)劃的方法

動態(tài)規(guī)劃方法是基于熱力學(xué)原理.當(dāng)RNA在一個穩(wěn)定的環(huán)境，自由能最小，我們可以理解為RNA二級結(jié)構(gòu)趨于穩(wěn)定.最典型的是Zuker動態(tài)規(guī)劃算法[4]，是自由能計算模型.該算法實(shí)現(xiàn)簡單，但它不能預(yù)測帶假結(jié)的RNA分子，由于其真實(shí)結(jié)構(gòu)可能不是最低自由能，所以用這種方法來預(yù)測準(zhǔn)確率低.

（2）比較序列法

比較序列的方法通常采用的是共變模型[5]和隨機(jī)上下文無關(guān)語法模型[6].共變模型，首先通過小規(guī)模的比對，之后更大規(guī)模的子樹和序列的比對概率被遞歸計算，直到得到最佳的比對.隨機(jī)上下文是由一定的語法“句子”定義的規(guī)則，然后通過這些句子的分析，得到堿基配對關(guān)系的序列，從而使RNA二級結(jié)構(gòu)得到預(yù)測[7].通過比較序列的方法可以預(yù)測RNA二級結(jié)構(gòu)更好，更準(zhǔn)確，但他們需要更多的同源序列，并且對同源序列還有一定的限制要求，花的時間也較多.

由于上述方法的局限性，組合優(yōu)化算法被提了出來.通過使用這種方法，遺傳算法[8-10]、模擬退火算法、Hopfield神經(jīng)網(wǎng)絡(luò)[11-12]等啟發(fā)式算法被用來解決這類問題.本文提出了一種混沌Hopfield神經(jīng)網(wǎng)絡(luò)算法，將其應(yīng)用于RNA二級結(jié)構(gòu)的預(yù)測.

1 免疫算法

免疫算法(Immune Algorithm,IA)是一種進(jìn)化算法，其靈感來自人體的免疫系統(tǒng).該算法模擬人體免疫系統(tǒng),是求解全局最優(yōu)解的一種新的優(yōu)化算法.記憶性和多樣性機(jī)制，使免疫算法的具有良好的全局優(yōu)化能力，很容易與其他方法結(jié)合，并得到很好的應(yīng)用.免疫算法主要由以下幾個部分構(gòu)成：

抗原：免疫算法中，抗原對應(yīng)目標(biāo)函數(shù)和約束條件.

抗體：免疫算法中，抗體對應(yīng)問題的解，可以隨機(jī)產(chǎn)生一組解，也可以使用特定的方法賦予一個初始解.

免疫記憶：與抗原有最大親和力的抗體加給記憶細(xì)胞.由于記憶細(xì)胞數(shù)量有限，新產(chǎn)生的與抗原親和力較低的抗體將被替換為親和力較高的抗體.在免疫算法中體現(xiàn)為較低親和力的解被替換為較高親和力的解.

免疫調(diào)節(jié)：高親和力抗體和高密度抗體分別受到促進(jìn)和抑制.在免疫算法中體現(xiàn)為在實(shí)施抗體的選擇過程中通過計算抗體存活的期望繁殖率.

通過下圖1可以清楚的看出免疫算法的一般步驟：

圖1 免疫算法流程

2 Hopfield神經(jīng)網(wǎng)絡(luò)

Hopfield神經(jīng)網(wǎng)絡(luò)稱為單層反饋網(wǎng)絡(luò)因其是一個只有單一的神經(jīng)元層次的結(jié)構(gòu)，同時每個神經(jīng)元與其他神經(jīng)元的輸出是相互連接的.0或者1是Hopfield神經(jīng)網(wǎng)絡(luò)的取值集合，yi(t+1)是神經(jīng)元的輸出，xi(t+1)是網(wǎng)絡(luò)的輸出，如公式(1)：

其中，Hopfield的輸出值保持為0或1是通過激勵函數(shù)實(shí)現(xiàn)的.

Hopfield神經(jīng)網(wǎng)絡(luò)在優(yōu)化計算的應(yīng)用中，目標(biāo)函數(shù)有相應(yīng)的能量函數(shù)，從而網(wǎng)絡(luò)權(quán)值也被確定，當(dāng)神經(jīng)網(wǎng)絡(luò)的能量達(dá)到最小時的解，就是問題的最優(yōu)解.

3 免疫Hopfield神經(jīng)網(wǎng)絡(luò)（IA-DHNN）優(yōu)化算法求解

3.1 RNA二級結(jié)構(gòu)中的Hopfield神經(jīng)網(wǎng)絡(luò)

Hopfield神經(jīng)網(wǎng)絡(luò)用于RNA二級結(jié)構(gòu)預(yù)測問題時，用基于最小自由能思想的莖區(qū)自由組合算法時，由于vi=0表示該神經(jīng)元被選中，能量函數(shù)可以寫成[13]：

其中，cij即為節(jié)點(diǎn)i和j間的權(quán)值，莖是否被選中決定了vi取0或1，ei表示莖i的能量；莖i與j是否相容來決定取值為0或1；非穩(wěn)定莖和穩(wěn)定莖間的相對率通過λ調(diào)整.

同時，第i個神經(jīng)元的動力方程為：

其中，dij取值0表示邊i和邊j不相交，取值為1時表示邊i和邊j相交.h(x)作為激勵函數(shù)，只有當(dāng)x=0時，h(x)=1.莖區(qū)x環(huán)長度用distance(x)表示.公式(3)中分為懲罰項(xiàng)和激勵項(xiàng)，懲罰項(xiàng)的權(quán)值參數(shù)A表示，激勵項(xiàng)的權(quán)值用B表示.

3.2 IA-DHNN算法描述

對于Hopfield神經(jīng)網(wǎng)絡(luò)來說，其對初始值的依賴性很強(qiáng)，因此本文使用距離函數(shù)和免疫算法的多樣性產(chǎn)生初始解，對神經(jīng)網(wǎng)絡(luò)的初始解進(jìn)行優(yōu)化，其中免疫算法通過產(chǎn)生若干代種群后，對其進(jìn)行聚類，使用聚類中心作為DHNN神經(jīng)元的初始輸出，更新其初始解和輸出值.其具體步驟如下：

（1）初始化，使目標(biāo)函數(shù)和約束條件有相應(yīng)的能量函數(shù)，問題的解為神經(jīng)元的輸出vi，令神經(jīng)網(wǎng)絡(luò)參數(shù)T=mmax，t=0；

（2）使用距離函數(shù)計算初始解，初始化神經(jīng)網(wǎng)絡(luò)；

（3）使用免疫算法產(chǎn)生80代抗體；

（4）采用K均值算法計算從免疫算法計算所得抗體的聚類中心；

（5）初始化神經(jīng)網(wǎng)絡(luò)，選取一個還未被訪問的聚類中心，為該神經(jīng)網(wǎng)絡(luò)神經(jīng)元的初始輸出；

（6）當(dāng)ui>0時，vi=1，否則vi=0.而vi=0說明該堿基配對；

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

（8）當(dāng)滿足終止條件，即滿足ui(t+1)=ui(t)+Δui(t) Δt或者Δui(t)或者t=max，繼續(xù)下一步,否則轉(zhuǎn)(5)；

（9）計算當(dāng)前解的目標(biāo)函數(shù)值；

（10）當(dāng)聚類中心全部被訪問過,停止計算,否則轉(zhuǎn)(4)；

（11）從中選取使目標(biāo)函數(shù)值最小的解.

4 實(shí)驗(yàn)結(jié)果

4.1 評價標(biāo)準(zhǔn)

敏感性（X），特異性（Y）[14]和馬休茲相互作用系數(shù)[15](MMC)是目前評價RNA二級結(jié)構(gòu)準(zhǔn)確率主要的3個度量參數(shù).X和Y分別是指所有堿基對在真實(shí)結(jié)構(gòu)中被正確預(yù)測到的比值和正確預(yù)測所有預(yù)測到的堿基對的比值.一般折中衡量上述兩個參數(shù)的是MCC.

其中，TP是堿基對正確預(yù)測的個數(shù)；FN是堿基對在真實(shí)結(jié)構(gòu)中存在，卻沒有被正確預(yù)測出的個數(shù)；FP是堿基對真實(shí)結(jié)構(gòu)中不存在，但被錯誤預(yù)測到的個數(shù)；TN是不配對堿基被正確預(yù)測的個數(shù).

4.2 參數(shù)設(shè)置和仿真結(jié)果比較

仿真中，A=0.1，B=0.2為神經(jīng)網(wǎng)絡(luò)的常量參數(shù).最后得到實(shí)驗(yàn)結(jié)果見下表1.我們可以看出本文的算法優(yōu)于其他算法.

表1 4種算法平均預(yù)測準(zhǔn)確率的比較

5 結(jié)語

本文根據(jù)免疫算法多樣性的有點(diǎn)，和神經(jīng)網(wǎng)絡(luò)對初值的依賴性，結(jié)合tRNA結(jié)構(gòu)的保守性的特點(diǎn)，對神經(jīng)網(wǎng)絡(luò)的初值進(jìn)行優(yōu)化，將免疫神經(jīng)網(wǎng)絡(luò)混合算法首次運(yùn)用于RNA二級結(jié)構(gòu)預(yù)測，全局的搜索能力得到提高，使其不易陷入局部最優(yōu)解，并獲得一定的效果.

〔1〕林娟,鐘一文,張駿.離散蛙跳算法預(yù)測RNA二級結(jié)構(gòu)[J].南京師范大學(xué)學(xué)報(工程技術(shù)版),2011 (04).

〔2〕邢翀.RNA二級結(jié)構(gòu)預(yù)測算法的研究[D].吉林大學(xué),2012.

〔3〕林娟,鐘一文.改進(jìn)的免疫粒子群優(yōu)化算法預(yù)測RNA二級結(jié)構(gòu)[J].計算機(jī)工程與應(yīng)用,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 網(wǎng)絡(luò)求解極大獨(dú)立集的莖區(qū)選擇算法以及在RNA 二級結(jié)構(gòu)預(yù)測中的應(yīng)用[J].計算機(jī)學(xué)報，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