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

摘要

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