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

吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (02): 452-0457.

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

余军^1,2,张长海^1,2,张浩^1,2,赵冠男^1,2,刘元宁^1,2

1.吉林大学计算机科学与技术学院长春 130012|2.吉林大学符号计算与知识工程教育部重点实验室长春 130012

收稿日期:2010-08-21 发布日期:2011-03-01
通讯作者: 刘元宁(1962-),男,教授,博士生导师.研究方向:生物信息学,模式识别.E-mail:liuyn@jlu.edu.cn E-mail:liuyn@jlu.edu.cn
作者简介:余军(1982-),男,博士研究生.研究方向:生物信息学,智能规划.E-mail:yujun2002359@163.com
基金资助:
国家自然科学基金项目(60971089); 高等学校博士学科点专项科研基金项目(20070183057).

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

YU Jun^1,2, ZHANG Chang-hai^1,2, ZHANG Hao^1,2, ZHAO Guan-nan^1,2, LIU Yuan-ning^1,2

1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2010-08-21 Published:2011-03-01

摘要/Abstract

摘要：

结合传统动态规划算法和组合优化算法在二级结构预测的优势, 提出了一种以茎区为最小结构单元的新的动态规划算法。对于给定的RNA序列, 首先得到所有可能的茎区集合, 采用环依赖的方式计算二级结构的能量, 通过茎区动态规划算法递归得到能量最优的二级结构，最后选取数据库中不同长度的已知二级结构的RNA序列进行测试。结果表明，该算法在特异性、敏感性和马休兹参数方面均优于遗传算法, 在计算复杂性方面低于传统的动态规划算法。

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

Abstract:

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.

Key words: computer application, bioinformatics, ribonucleic acid(RNA), secondary structure, stems, dynamic programming algorithm

中图分类号:

TP301

余军, 张长海, 张浩, 赵冠男, 刘元宁. 基于茎区的动态规划算法的核糖核酸二级结构预测[J]. 吉林大学学报(工学版), 2011, 41(02): 452-0457.

YU Jun, ZHANG Chang-Hai, ZHANG Hao, ZHAO Guan-Nan, LIU Yuan-Ning. Prediction of RNA secondary structure using dynamic programming algorithm based on stems[J]. 吉林大学学报(工学版), 2011, 41(02): 452-0457.

参考文献

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed