|
|||||
|
|
| 基于局部茎搜索的RNA二级结构预测算法 | |
| 引用本文： | 陈翔,卜东波,张法,高文.基于局部茎搜索的RNA二级结构预测算法[J].生物化学与生物物理进展,2009,36(1):115-121. |
| 作者姓名： | 陈翔 卜东波 张法 高文 |
| 作者单位： | 1. 中国科学院智能信息处理重点实验室,北京,100190;中国科学院计算技术研究所,北京,100190;中国科学院研究生院,北京,100049 2. 中国科学院计算技术研究所,北京,100190 3. 中国科学院智能信息处理重点实验室,北京,100190;中国科学院计算技术研究所,北京,100190 4. 京大学信息科学技术学院,北京,100080 |
| 基金项目： | 国家重点基础研究发展计划(973)资助项目(2002CB713807)，中国科学院前沿知识创新项目(20076020)和国家自然科学基金资助项目(60503060，90612019，60752001). |
| 摘 要： | RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题，基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法．但RNA结构中假结的存在使MFE问题理论上成为一个NP-hard问题，即使采用动态规划等优化算法也会面临时间复杂度高的困难，同时研究还发现，由于受RNA折叠动力学机制以及环境因素的影响，真实的RNA二级结构往往并不处于自由能最小状态．根据RNA折叠的特点，提出了一种启发式搜索算法来预测带假结的RNA二级结构．该算法以RNA的茎为基本单元，采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构，该算法不仅能显著降低搜索RNA二级结构的时间复杂度，还有助于弥补单纯依赖能量预测RNA二级结构的不足．在多种类型的RNA标准数据集上进行了检验，结果表明，该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率． |
| 关 键 词： | RNA二级结构预测 假结 启发式算法 |
| 收稿时间： | 5/6/2008 12:00:00 AM |
| 修稿时间： | 7/3/2008 12:00:00 AM |
A Local-stem-search Algorithm to Predict The RNA Secondary Structure |
|
| CHEN Xiang,BU Dong-Bo,ZHANG Fa and GAO Wen.A Local-stem-search Algorithm to Predict The RNA Secondary Structure[J].Progress In Biochemistry and Biophysics,2009,36(1):115-121. | |
| Authors: | CHEN Xiang BU Dong-Bo ZHANG Fa and GAO Wen |
| Abstract: | |
| Keywords: | NP-hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《生物化学与生物物理进展》浏览原始摘要信息 | |
| 点击此处可从《生物化学与生物物理进展》下载免费的PDF全文 | |