基于遗传模拟退火混合算法的RNA二级结构预测

黄进 宋余庆 凌青华

摘要：RNA二级结构预测是生物信息学中非常重要的内容。RNA二级结构的准确预测有助于生物研究者了解RNA分子在生物体内中所起到的重要作用。近年来，基于最小自由能模型的启发式算法常被运用于预测RNA二级结构。遗传算法和模拟退火算法是常见的启发式算法，将遗传算法中的遗传变异机制以及模拟退火的退火机制相结合，形成一种新的算法，以茎区作为种群中的个体进行交叉变异操作，将所得到的结果进行退火操作，从而得到最优解。该算法结合了遗传算法和模拟退火算法的优势，实验结果表明，该方法预测结果具有较高的精度。

关键词：RNA二级结构；最小自由能；茎区；遗传算法；模拟退火算法

DOIDOI：10.11907/rjdk.161267

中图分类号：TP312文献标识码：A文章编号：1672-7800（2016）006-0027-04

参考文献：

[1]邹权，郭茂祖，张涛涛. RNA二级结构预测方法综述[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二级结构预测算法.计算机工程与应用，2007，43（3）：26-29.

[6]刘琦，张引，叶修梓. 基于离散Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用[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]陈涛.基于茎区的RNA 二级结构预测方法研究[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二级结构中假结的预测研究[D]. 长春：吉林大学，2013.

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

[16]林娟.RNA二级结构预测的群智能优化算法研究[D].福州：福建农林大学，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二级结构预测的研究[D].成都：电子科技大学，2010.

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