title: Counting RNA pseudoknotted structures.
abstract: In 2004, Condon and coauthors gave a hierarchical classification of exact RNA structure prediction algorithms according to the generality of structure classes that they handle. We complete this classification by adding two recent prediction algorithms. More importantly, we precisely quantify the hierarchy by giving closed or asymptotic formulas for the theoretical number of structures of given size n in all the classes but one. This allows us to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms.
authors.affiliation: LRI, Université Paris-Sud and CNRS, Orsay Cedex, France.
authors.forename: Cédric
authors.initials: C
authors.lastname: Saule
authors.forename: Mireille
authors.initials: M
authors.lastname: Régnier
authors.forename: Jean-Marc
authors.initials: JM
authors.lastname: Steyaert
authors.forename: Alain
authors.initials: A
authors.lastname: Denise
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D011336:Probability; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA
chemical_list: D012313:RNA