基于免疫與神經網絡的RNA二級結構預測*

林 航,李金銘

(福建農林大學,福建 福州 350002)

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

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

(1)動態規劃的方法

動態規劃方法是基于熱力學原理。Zuker動態規劃算法為代表的[4]的動態規劃算法，是自由能計算模型。該算法實現簡單，但它不能預測帶假結的RNA分子，由于其真實結構可能不是最低自由能，所以用這種方法來預測準確率低。

(2)比較序列法

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

由于上述方法的局限性，組合優化算法被提了出來。通過使用這種方法，模擬退火算法、遺傳算法[7-9]、Hopfield神經網絡[10-11]等啟發式算法被用來解決該問題。本文采用混沌Hopfield神經網絡算法預測RNA二級結構。

一、混沌理論

混沌是一種非線性現象，廣泛存在于自然界中，它可能看起來有些混亂，但其精致的結構，使隨機性、遍歷性和規律性成為它的特點，某個范圍內，其可以按自身的規律不重復遍歷所有狀態。

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

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

(1)

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

二、Hopfield神經網絡

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

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

(2)

Hopfield神經網絡在優化計算的應用中，目標函數有相應的能量函數，從而網絡權值也被確定，當神經網絡的能量達到最小時的解，就是問題的最優解。

三、混沌Hopfield神經網絡優化算法求解

1.應用于RNA二級結構預測的Hopfield神經網絡Hopfield神經網絡用于RNA二級結構預測問題時，用基于最小自由能思想的莖區自由組合算法時，由于Vi=0表示該神經元被選中，能量函數可以寫成[12]：

(3)

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

2.混沌Hofield神經網絡算法描述

對于Hopfield神經網絡來說，其對初始值的依賴性很強，因此本文使用距離函數產生初始解，對神經網絡的初始解進行優化。對Hopfield初步產生的最優解，通過使用混沌函數對其值進行混沌化，使其跳出局部最優解，搜索全局最優解，其具體步驟如下：

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

(2) 使用距離函數計算初始解，初始化神經網絡；

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

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

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

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

(7) 計算當前解的目標函數值；

(8) 使用混沌函數對初步初始解進行混沌化，產生新的初始值初始化神經網絡;

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

四、實驗結果

1. 評價標準

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

2. 參數設置和仿真結果比較

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

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

五、 結語

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

參考文獻：

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

[2] 邢翀. RNA二級結構預測算法的研究[D].長春：吉林大學,2012.

[3] 林娟,鐘一文. 改進的免疫粒子群優化算法預測RNA二級結構[J].計算機工程與應用, 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網絡求解極大獨立集的莖區選擇算法以及在RNA二級結構預測中的應用[J]. 計算機學報，2008, 31(1): 51～58.