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

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

Graph grammars of RNA secondary structure classes with pseudoknots

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.