Counting RNA pseudoknotted structures (extended abstract)

Cédric Saule 1, 2 Mireille Regnier 3, 4 Jean-Marc Steyaert 4, 3 Alain Denise 1, 5, 3
3 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 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 to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms. \par
Liste complète des métadonnées

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01186262
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 24, 2015 - 3:45:54 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Document(s) archivé(s) le : Wednesday, November 25, 2015 - 5:06:02 PM

File

dmAN0180.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01186262, version 1

Citation

Cédric Saule, Mireille Regnier, Jean-Marc Steyaert, Alain Denise. Counting RNA pseudoknotted structures (extended abstract). 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. pp.1037-1048. ⟨hal-01186262⟩

Share

Metrics

Record views

297

Files downloads

329