Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications
Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications
复制标题
DOI：
10.1089/cmb.2011.0094
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
M. Nebel;Frank Weinberg
中科院分区：
文献类型：
--
作者：
M. Nebel;Frank Weinberg
预测具有伪结的RNA结构一般是NP完全问题。因此，一些作者提出了通过允许（分别地，不允许）某些结构动机来提供多项式时间预测算法的子类。在这篇文章中，我们介绍了一个统一的代数观点，对大多数这些类。这样就有可能找到线性时间识别算法，来决定给定的结构是否是类的成员（我们将这些算法作为Web服务提供给科学界）。此外，通过提出一个一般的翻译计划，我们的代数描述到多个上下文无关文法，并证明了一个新的对应关系的多个上下文无关文法和生成函数，它成为可能，以获得精确的渐近大小的所有类，解决了一些公开的问题，如枚举的里瓦斯& Eddy类的pseudoknots。
Predicting RNA structures with pseudoknots in general is an NP-complete problem. Accordingly, several authors have suggested subclasses that provide polynomial time prediction algorithms by allowing (respectively, disallowing) certain structural motives. In this article, we introduce a unifying algebraic view on most of these classes. That way it becomes possible to find linear time recognition algorithms that decide whether or not a given structure is member of a class (we offer these algorithms as a web service to the scientific community). Furthermore, by presenting a general translation scheme of our algebraic descriptions into multiple context-free grammars, and proving a new correspondence of multiple context-free grammars and generating functions, it becomes possible to derive the precise asymptotic size of all the classes, solving some open problems such as enumerating the Rivas & Eddy class of pseudoknots.