关键词: 假结, 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