计算机应用 ›› 2010, Vol. 30 ›› Issue (06): 1694-1697.

• 典型应用 • 上一篇    下一篇

基于茎区组合的RNA二级结构预测算法

骆嘉伟1,陈涛2   

  1. 1. 湖南大学
    2. 湖南大学计算机与通信学院
  • 收稿日期:2009-12-01 修回日期:2010-01-26 发布日期:2010-06-01 出版日期:2010-06-01
  • 通讯作者: 陈涛
  • 基金资助:
    新型表达模式下的功能基因分析算法研究;基于聚类的基因功能预测方法

RNA secondary structure prediction algorithm based on steam-combination

  • Received:2009-12-01 Revised:2010-01-26 Online:2010-06-01 Published:2010-06-01

摘要: RNA二级结构预测是生物信息学的研究热点和难点,特别是对于含假结的RNA二级结构的预测,已经被证明是NP问题。根据RNA折叠的特点,提出了一种基于茎区组合的智能优化算法来预测RNA 的二级结构。该算法以RNA的茎区为基本单元,结合图论思想,通过二元关系的基本理论,依据自由能最小原则获取茎区的最优组合。该算法的时间复杂度为O(n3),空间复杂度为O(n2),而且可以发现假结。实验结果证明了算法的有效性。

关键词: RNA二级结构, 茎区, 假结, 拟序集, 极大链

Abstract: RNA secondary structure prediction is the hot topic in bioinformatics. Especially, the RNA secondary structure prediction with pseudoknot has been proved a NP-hard problem. According to the characteristics of RNA folding, a heuristic algorithm — QuasiRP to predict RNA secondary structure was presented. Using stem as the unit, combining graph theory and fundamental theory of binary relations, QuasiRP can find the optimal stem-combination based on Minimal Free Energy (MFE) criterion. The time complexity is O(n3) while the space complexity is O(n2), and pseudoknot can be found. The results show the validity of the algorithm.

Key words: RNA secondary structure, stem, pseudoknot, quasi-order set (QOS), maximal chain