基于免疫與神經(jīng)網(wǎng)絡(luò)的RNA二級結(jié)構(gòu)預(yù)測*

林 航,李金銘

(福建農(nóng)林大學(xué),福建 福州 350002)

脫氧核糖核酸具有重要的生物學(xué)功能，是DNA到蛋白質(zhì)間遺傳信息中間傳遞體[1]。RNA二級結(jié)構(gòu)是特定平面圖，配對的部分構(gòu)成局部的雙螺旋結(jié)構(gòu)，這就是RNA的二級結(jié)構(gòu)[2]，它是一種平面的結(jié)構(gòu)。目前，使用實驗方法在RNA信息數(shù)據(jù)的驚人的增長下，實現(xiàn)生物分子的具體的二級結(jié)構(gòu)有著其自身的局限性，而且對所有分子并不是都有效的[3]。

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

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

動態(tài)規(guī)劃方法是基于熱力學(xué)原理。Zuker動態(tài)規(guī)劃算法為代表的[4]的動態(tài)規(guī)劃算法，是自由能計算模型。該算法實現(xiàn)簡單，但它不能預(yù)測帶假結(jié)的RNA分子，由于其真實結(jié)構(gòu)可能不是最低自由能，所以用這種方法來預(yù)測準確率低。

(2)比較序列法

比較序列的方法通常采用的是共變模型[5]和隨機上下文無關(guān)語法模型[6]。通過比較序列的方法可以預(yù)測RNA二級結(jié)構(gòu)更好，更準確，但他們需要更多的同源序列，并且對同源序列還有一定的限制要求，花的時間也較多。

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

一、混沌理論

混沌是一種非線性現(xiàn)象，廣泛存在于自然界中，它可能看起來有些混亂，但其精致的結(jié)構(gòu)，使隨機性、遍歷性和規(guī)律性成為它的特點，某個范圍內(nèi)，其可以按自身的規(guī)律不重復(fù)遍歷所有狀態(tài)。

一般指的是通過隨機確定性方程獲得的隨機性運動狀態(tài)，混沌狀態(tài)變量被稱為混沌變量。logistic映射是是一個常用的混沌系統(tǒng)，方程如下：

Zn+1=μzn(1-zn) n=0,1,…n

(1)

式(1)是一個動力學(xué)系統(tǒng)，μ作為其控制參數(shù)。μ值確定后，從任意的初值 z0∈[0,1]，可以迭代得到一個確定的時間序列Z0,Z1，…Zn。 當(dāng)μ=4 時，是一個完全處于混沌狀態(tài)系統(tǒng)?；煦鐑?yōu)化算法能夠輕易的跳出局部最優(yōu)解，歸功于它的混沌性。它的搜索機制表現(xiàn)很好，常常被用于算法的混合中，并作了廣泛研究。把混沌算子應(yīng)用于遺傳算法中，提出了混沌遺傳算法，取得了較好的效果。把混沌搜索結(jié)合于微粒群算法，得到了混沌粒子群優(yōu)化算法，都具有很好的搜索性能。

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

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

Xi(t+1)=sgn(yi(t+1),i∈[1,n]

(2)

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

三、混沌Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法求解

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

(3)

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

2.混沌Hofield神經(jīng)網(wǎng)絡(luò)算法描述

對于Hopfield神經(jīng)網(wǎng)絡(luò)來說，其對初始值的依賴性很強，因此本文使用距離函數(shù)產(chǎn)生初始解，對神經(jīng)網(wǎng)絡(luò)的初始解進行優(yōu)化。對Hopfield初步產(chǎn)生的最優(yōu)解，通過使用混沌函數(shù)對其值進行混沌化，使其跳出局部最優(yōu)解，搜索全局最優(yōu)解，其具體步驟如下：

(1) 定義問題，能量函數(shù)對應(yīng)目標函數(shù)和約束條件，神經(jīng)元的輸出 Vi對應(yīng)問題的解，初始化神經(jīng)網(wǎng)絡(luò)參數(shù)，令 T=max,t=0 ；

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

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

(4) 當(dāng)Ui>0 時，Vi=1 ，否則 Vi=0。而 Vi=0說明該堿基配對；

(5) 使用公式(4)中的定義的更新Ui，Vi；

(6) 當(dāng)滿足終止條件，即滿足Ui(t+1)=Ui(t)+△Ui(t)△t或者△ Ui(t)或者t=max ，繼續(xù)下一步, 否則轉(zhuǎn)4)；

(7) 計算當(dāng)前解的目標函數(shù)值；

(8) 使用混沌函數(shù)對初步初始解進行混沌化，產(chǎn)生新的初始值初始化神經(jīng)網(wǎng)絡(luò);

(9) 達到最大迭代次數(shù)，優(yōu)化終止，從中選取使目標函數(shù)值最小的解。

四、實驗結(jié)果

1. 評價標準

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

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

仿真中，A=0.1,B=0.2 為神經(jīng)挽留過的常量參數(shù)。最后得到實驗結(jié)果見下表1。我們可以看出本文的算法優(yōu)于其他算法。

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

五、 結(jié)語

本文根據(jù)混沌算法的遍歷性和隨機性，和神經(jīng)網(wǎng)絡(luò)對初值的依賴性，結(jié)合RNA結(jié)構(gòu)的保守性的特點，對神經(jīng)網(wǎng)絡(luò)的初值進行優(yōu)化，將Hofield神經(jīng)網(wǎng)絡(luò)通過混沌函數(shù)進行優(yōu)化，首次運用于RNA二級結(jié)構(gòu)預(yù)測，提高了全局，搜索能力，使其不易陷入局部最優(yōu)解，并獲得一定的效果。

參考文獻：

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

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

[3] 林娟,鐘一文. 改進的免疫粒子群優(yōu)化算法預(yù)測RNA二級結(jié)構(gòu)[J].計算機工程與應(yīng)用, 2012，(1).

[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: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]劉琦，張引，葉修梓. 基于離散Hopfield網(wǎng)絡(luò)求解極大獨立集的莖區(qū)選擇算法以及在RNA二級結(jié)構(gòu)預(yù)測中的應(yīng)用[J]. 計算機學(xué)報，2008, 31(1): 51～58.