基于局部茎搜索的RNA二级结构预测算法
RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法.但RNA结构中假结的存在使MFE问题理论上成为一个NP-bard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态.根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构.该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构,该算法不仅能显著降低搜索RNA二级结构的时间复杂度,还有助于弥补单纯依赖能量预测RNA二级结构的不足.在多种类型的RNA标准数据集上进行了检验,结果表明,该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率.
RNA二级结构预测、假结、NP-hard、启发式算法
36
TP319;Q7(计算技术、计算机技术)
国家重点基础研究发展计划973资助项目2002CB713807;中国科学院前沿知识创新项目20076020;国家自然科学基金资助项目60503060,90612019,60752001
2009-03-31（万方平台首次上网日期，不代表论文的发表时间）
共7页
115-121
