On the Generative Power of Grammars for RNA Secondary Structure
On the Generative Power of Grammars for RNA Secondary Structure
复制标题
论 RNA 二级结构语法的生成能力
DOI：
10.1093/ietisy/e88-d.1.53
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
T. Kasami
中科院分区：
文献类型：
--
作者：
Yuki Kato;H. Seki;T. Kasami
目前已经提出了几种表示RNA伪结二级结构的语法，如简单线性树邻接语法（sl-tag）、扩展sl-tag （esl-tag）和RNA伪结语法（rpg）。本文的主要目的是通过将这些语法识别为多个上下文无关语法（mcfg）的子类来比较它们的生成能力。具体来说，由esl-tag生成的语言类（ESL-TAL）恰当地包括由sl-tag生成的语言类（SL-TAL）和由cfg生成的语言类。此外，我们还证明了rpg生成的语言类与mcfg生成的维度为1或2、排名为1或2的语言类是一致的。结果表明，SL-TAL是一个全三联体，而ESL-TAL是一个取代闭合全AFL。关键词：RNA二级结构；伪结；多重上下文无关语法
Several grammars have been proposed for representing RNA secondary structure including pseudoknots such as simple linear tree adjoining grammar (sl-tag), extended sl-tag (esl-tag) and RNA pseudoknot grammar (rpg). The main purpose of this paper is to compare the generative power of these grammars by identifying them as subclasses of multiple context-free grammars (mcfg). Specifically, it is shown that the class of languages generated by esl-tag (ESL-TAL) properly includes the class of languages generated by sl-tag (SL-TAL) and the class of languages generated by cfg. Also, we show that the class of languages generated by rpg coincides with the class of languages generated by mcfg with dimension one or two and rank one or two. Furthermore, it is shown that SL-TAL is a full trio and ESL-TAL is a substitution closed full AFL. key words: RNA secondary structure, pseudoknot, multiple context-free grammar, tree adjoining grammar