基于局部茎搜索的RNA二级结构预测算法

• 作者: 卜东波 张法 陈翔 高文
• 来源期刊: 生物化学与生物物理进展
• 学科: 工学
• 关键词: RNA二级结构预测 假结 NP-hard 启发式算法
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 技术与方法
• 页码范围: 115-121
• 页数: 7页
• 分类号: TP319|Q7
• 字数: 6024字
• 语种: 中文
• DOI: 10.3724/SP.J.1206.2008.00329

摘要

RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法.但RNA结构中假结的存在使MFE问题理论上成为一个NP-bard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态.根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构.该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构,该算法不仅能显著降低搜索RNA二级结构的时间复杂度,还有助于弥补单纯依赖能量预测RNA二级结构的不足.在多种类型的RNA标准数据集上进行了检验,结果表明,该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卜东波	中国科学院计算技术研究所	13	455	7.0	13.0
2	张法	中国科学院智能信息处理重点实验室	15	156	5.0	12.0
6	陈翔	中国科学院智能信息处理重点实验室	25	268	8.0	16.0
15	高文	京大学信息科学技术学院	1	7	1.0	1.0