Counting RNA pseudoknotted structures

Cédric Saule 1, 2 Mireille Regnier 1, 3, * Jean-Marc Steyaert 1, 3 Alain Denise 1, 2
* Corresponding author
1 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
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 algo- rithms. 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 to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms.
Complete list of metadatas
Contributor : Mireille Regnier <>
Submitted on : Friday, November 26, 2010 - 10:05:50 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Sunday, February 27, 2011 - 2:39:11 AM


Files produced by the author(s)




Cédric Saule, Mireille Regnier, Jean-Marc Steyaert, Alain Denise. Counting RNA pseudoknotted structures. Journal of Computational Biology, Mary Ann Liebert, 2011, 18 (10), pp.1339-1351. ⟨10.1089/cmb.2010.0086⟩. ⟨inria-00537117⟩



Record views


Files downloads