计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (2): 23-25.

• 博士论坛 • 上一篇    下一篇

含假结RNA二级结构类的图语法

高世乐,丁克诠   

  1. 大连理工大学 电子与信息工程学院,辽宁 大连 116024
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-11 发布日期:2008-01-11
  • 通讯作者: 高世乐

Graph grammars of RNA secondary structure classes with pseudoknots

GAO Shi-le,DING Ke-quan   

  1. School of Electronic and Information Engineering,Dalian University of Technology,Dalian,Liaoning 116024,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-11 Published:2008-01-11
  • Contact: GAO Shi-le

摘要: 用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。

关键词: 假结, RNA二级结构, 重写规则, 图语法

Abstract: Computational prediction of the Minimum Free Energy(MFE) secondary structure of an RNA molecule from its base sequence is NP-hard for pseudoknots.In recent years,several polynomial algorithms have been proposed that find the MFE secondary structure from a restricted class of secondary structures.The author proposes a kind of RNA secondary structure graph grammar which composed by the set of initial structure graphs and the set of the rewriting rules.All the structure graphs which generated from the continuous rewriting of these rules on initial structure graphs are languages of the graph grammar.The author proposes 5 graph grammars to represent 5 target classes of typical prediction algorithms,it makes the structure feature of the target classes clear and makes the proper inclusive relation between the classes be found lightly.

Key words: pseudoknots, RNA secondary structures, rewriting rules, graph grammars