基于遺傳模擬退火混合算法的RNA二級結(jié)構(gòu)預測

黃進 宋余慶 凌青華

摘要：RNA二級結(jié)構(gòu)預測是生物信息學中非常重要的內(nèi)容。RNA二級結(jié)構(gòu)的準確預測有助于生物研究者了解RNA分子在生物體內(nèi)中所起到的重要作用。近年來，基于最小自由能模型的啟發(fā)式算法常被運用于預測RNA二級結(jié)構(gòu)。遺傳算法和模擬退火算法是常見的啟發(fā)式算法，將遺傳算法中的遺傳變異機制以及模擬退火的退火機制相結(jié)合，形成一種新的算法，以莖區(qū)作為種群中的個體進行交叉變異操作，將所得到的結(jié)果進行退火操作，從而得到最優(yōu)解。該算法結(jié)合了遺傳算法和模擬退火算法的優(yōu)勢，實驗結(jié)果表明，該方法預測結(jié)果具有較高的精度。

關鍵詞：RNA二級結(jié)構(gòu)；最小自由能；莖區(qū)；遺傳算法；模擬退火算法

DOIDOI：10.11907/rjdk.161267

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2016）006-0027-04

參考文獻：

[1]鄒權(quán)，郭茂祖，張濤濤. RNA二級結(jié)構(gòu)預測方法綜述[J]. 電子學報，2008，36（2）： 331-337.

[2]TINOCO I，UHLENBECK O C， LEVINE M D. Estimation of secondary structure in ribonucleic acids[J]. Nature， 1971， 230（5293）： 362-367.

[3]RUTH NUSSINOV，GEORGE PIECZENIK，JERROLD R GRIGGS，et al.Algorithms for loop matchings[J].SIAM Journal on Applied Mathematics，1978，35（1）：68-82.

[4]ZUKER M， STIEGLER P. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information[J]. Nucleic acids research，1981，9（1）：133-148.

[5]胡桂武，彭宏.基于免疫粒子群集成的RNA二級結(jié)構(gòu)預測算法.計算機工程與應用，2007，43（3）：26-29.

[6]劉琦，張引，葉修梓. 基于離散Hopfield網(wǎng)絡求解極大獨立集的莖區(qū)選擇算法以及在RNA二級結(jié)構(gòu)預測中的應用[J]. 計算機學報，2008，31（1）： 51-58.

[7]DAVID H MATHEWS， JEFFRET SABINA， MICHAEL ZUKER， et al . Expand sequence dependence of thermodynamic parameters improves prediction of RNA secondary structured [J]. Journal of Molecular Biology， 1999， 288（5）：911-940.

[8]ELENA RIVAS， SEAN R EDDY.A dynamic programming algorithm for RNA structure prediction including pseudoknots[J]. Journal of Molecular Biology， 1999， 285 （5）：2053-2068.

[9]KAY C， WIESE E， GLEN. A permutation-based genetic algorithm for the RNA folding problem：a critical look at selection strategies，crossover operators and representation issues[J].BioSystems， 2003， 72（1）：29-41.

[10]陳濤.基于莖區(qū)的RNA 二級結(jié)構(gòu)預測方法研究[D].長沙：湖南大學，2011.

[11]REN J， RASTEGARI B， CONDON A， et al. Hotknots heuristic prediction of RNA secondary structures including pseudoknots[J].RNA， 2005， 11（10）： 1494-1504.

[12]DOUGLAS H TURNER.Approximation algorithm of the RNA pseudoknotted structure prediction based on MFE[C]. IEEE International Conference on Information and Automation，2013：1044-1048.

[13]HYONEMOTO，KASAI. A semi_supervised learning approach for RNA secondary structure prediction[J].Computational Biology and Chemistry，2015（57）：72-79.

[14]楊赫. RNA二級結(jié)構(gòu)中假結(jié)的預測研究[D]. 長春：吉林大學，2013.

[15]RICHARD BEAL，DONALD ADJEROH.Efficient pattern matching for RNA secondary structure[J]. Theoretical Computer Science，2015（592）：59-71.

[16]林娟.RNA二級結(jié)構(gòu)預測的群智能優(yōu)化算法研究[D].福州：福建農(nóng)林大學，2011.

[17]BALDI P，BRUNAK S，CHAUVIN Y，et al.Assessing the accuracy of prediction algorithms for classication： an overviews[J]. Bioinformatics，2000，16（5）：412-424.

[18]VAN BATENBURG F H D，GULTYAEV A P，PLEIJ C W A.An APL-programmed genetic algorithm for the prediction of RNA secondary structure[J].Journal of theoretical Biology，1995，174（3）：269-280.

[19]GARDNER PP，GIEGERICH R.A comprehensive comparison of comparative RNA structure prediction approaches[J]. BMC Bioinformatics， 2004， 5 （1）：1-32.

[20]胥杰. 基于混沌模擬退火算法的RNA二級結(jié)構(gòu)預測的研究[D].成都：電子科技大學，2010.

[21]E TEN DAM，K PLEIJ，D DRAPER.Structural and functionalaspects of RNA pseudoknots[J]. Biochemistry， 1992，31（47）：11665-11676.