基于局部茎搜索的RNA二级结构预测算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家重点基础研究发展计划(973)资助项目(2002CB713807),中国科学院前沿知识创新项目(20076020)和国家自然科学基金资助项目(60503060,90612019,60752001).


A Local-stem-search Algorithm to Predict The RNA Secondary Structure
Author:
Affiliation:

Fund Project:

This work was supported by grants from National Basic Research Program of China(2002CB713807), Frontier Project of Knowledge Innovation Program of The Chinese Academy of Sciences(20076020) and The National Natural Science Foundation of China(60503060, 90612019, 60752001).

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    RNA secondary structure predicting is a classical problem in bioinformatics and the optimal algorithms based on minimal free energy (MFE) criterion are the widely used methods. However, pseudoknots render the problem of computing the RNA MFE structure with pseudoknot becomes a NP-hard problem. A heuristic algorithm——StemFind to predict RNA secondary structure with pseudoknot was presented. The algorithm regard stem as the basic search unit, adopting heuristic search strategy, and search the most possible RNA secondary structure in stem combination space. The StemFind algorithm to a large number of test sets was applied. Performance evaluation demonstrates that StemFind not only outperforms the well-known optimal and heuristic algorithms in overall sensitivity and specificity but also requires significantly less time than the optimal algorithm.

    参考文献
    相似文献
    引证文献
引用本文

陈翔,卜东波,张法,高文.基于局部茎搜索的RNA二级结构预测算法[J].生物化学与生物物理进展,2009,36(1):115-121

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2008-05-06
  • 最后修改日期:2008-07-03
  • 接受日期:
  • 在线发布日期: 2008-11-03
  • 出版日期: 2009-01-20