Algebraic and combinatorial properties of common RNA pseudoknot classes with applications.
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.
Computer Science Department, University of Kaiserslautern, Gottlieb Daimler Str. 48, Kaiserslautern 67663, Germany. nebel@informatik.uni-kl.de
Markus E
ME
Nebel
Frank
F
Weinberg
D000465:Algorithms; D008956:Models, Chemical; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry / Q000235:genetics
D012313:RNA