Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications

作者：Nebel Markus E^*; Weinberg Frank

来源：Journal of Computational Biology, 2012, 19(10): 1134-1150.

DOI：10.1089/cmb.2011.0094

• algorithms
• combinatorics
• RNA
• secondary structure

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.

• 出版日期2012-10