Counting RNA pseudoknotted structures

Cédric Saule 1, 2 Mireille Regnier 1, 3, * Jean-Marc Steyaert 1, 3 Alain Denise 1, 2
* Auteur correspondant
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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
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.
Type de document :
Article dans une revue
Journal of Computational Biology, Mary Ann Liebert, 2011, 18 (10), pp.1339-1351. 〈10.1089/cmb.2010.0086〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00537117
Contributeur : Mireille Regnier <>
Soumis le : vendredi 26 novembre 2010 - 10:05:50
Dernière modification le : jeudi 10 mai 2018 - 02:06:35
Document(s) archivé(s) le : dimanche 27 février 2011 - 02:39:11

Fichier

JCB10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

517

Téléchargements de fichiers

168