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

Graph grammars of RNA secondary structure classes with pseudoknots

作　　者：高世乐[1] 丁克诠[1] 

机构地区：[1]大连理工大学电子与信息工程学院,辽宁大连116024

出　　处：《计算机工程与应用》2008年第2期23-25,105,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.A0324670) 。

摘　　要：用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。Computational prediction of the Minimum Free Energy （MFE） secondary structure of an RNA molecule from its base sequence is NP-hard for pseudoknots.ln 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.

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

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构] Q71[自动化与计算机技术—计算机科学与技术]