基于茎区的动态规划算法的核糖核酸二级结构预测  

Prediction of RNA secondary structure using dynamic programming algorithm based on stems

作　　者：余军[1,2] 张长海[1,2] 张浩[1,2] 赵冠男[1,2] 刘元宁[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《吉林大学学报（工学版）》2011年第2期452-457,共6页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60971089);高等学校博士学科点专项科研基金项目(20070183057)

摘　　要：结合传统动态规划算法和组合优化算法在二级结构预测的优势,提出了一种以茎区为最小结构单元的新的动态规划算法。对于给定的RNA序列,首先得到所有可能的茎区集合,采用环依赖的方式计算二级结构的能量,通过茎区动态规划算法递归得到能量最优的二级结构,最后选取数据库中不同长度的已知二级结构的RNA序列进行测试。结果表明,该算法在特异性、敏感性和马休兹参数方面均优于遗传算法,在计算复杂性方面低于传统的动态规划算法。In this paper,a new method is presented to predict the RNA secondary structure,which combines the characteristics and advantages of combinatorial optimization approach and traditional dynamic programming algorithm.First,for a given RNA sequence,the set containing all possible stems is obtained.Then,adopting what are called loop dependent energy rules,the secondary structure is constructed using dynamic programming algorithm based on stems.The proposed program was tested by the case with RNA sequences.Experiment results show that the proposed program is better than genetic algorithm in terms of specificity,sensitivity and Matthews correlation coefficient,and the complexity of the program is lower than that of traditional dynamic programming algorithm.

关 键 词：计算机应用 生物信息学 核糖核酸 二级结构 茎区 动态规划算法 

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