基于茎区组合的RNA二级结构预测算法  

RNA secondary structure prediction algorithm based on steam-combination

作　　者：骆嘉伟[1] 陈涛[1] 

机构地区：[1]湖南大学计算机与通信学院,长沙410082

出　　处：《计算机应用》2010年第6期1694-1697,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60873184);湖南省自然科学基金资助项目(07JJ5086)

摘　　要：RNA二级结构预测是生物信息学的研究热点和难点,特别是对于含假结的RNA二级结构的预测,已经被证明是NP问题。根据RNA折叠的特点,提出了一种基于茎区组合的智能优化算法来预测RNA的二级结构。该算法以RNA的茎区为基本单元,结合图论思想,通过二元关系的基本理论,依据自由能最小原则获取茎区的最优组合。该算法的时间复杂度为O(n3),空间复杂度为O(n2),而且可以发现假结。实验结果证明了算法的有效性。RNA secondary structure prediction is the hot topic in bioinformatics.Especially,the RNA secondary structure prediction with pseudoknot has been proved a NP-hard problem.According to the characteristics of RNA folding,a heuristic algorithm — QuasiRP to predict RNA secondary structure was presented.Using stem as the unit,combining graph theory and fundamental theory of binary relations,QuasiRP can find the optimal stem-combination based on Minimal Free Energy （MFE） criterion.The time complexity is O（n3） while the space complexity is O（n2）,and pseudoknot can be found.The results show the validity of the algorithm.

关 键 词：RNA二级结构 茎区 假结 拟序集 极大链 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]