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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Résumé : En 2004, Condon et ses coauteurs ont défini une classification des algorithmes exacts de prédiction de structure d'ARN, selon le degré de généralité des classes de structures qu'ils sont capables de prédire. Nous complétons cette classification en y ajoutant deux algorithmes récents. Chose plus importante, nous quantifions la hiérarchie des algorithmes, en donnant des formules closes ou asymptotiques pour le nombre théorique de structures de taille donnée n dans chacune des classes, sauf une. Ceci fournit un moyen d'évaluer, pour chaque algorithme, le compromis entre son degré de généralité et sa complexité.
Type de document :
Communication dans un congrès
Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.1037-1048, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01186262
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 24 août 2015 - 15:45:54
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08
Document(s) archivé(s) le : mercredi 25 novembre 2015 - 17:06:02

Fichier

dmAN0180.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01186262, version 1

Citation

Cédric Saule, Mireille Regnier, Jean-Marc Steyaert, Alain Denise. Counting RNA pseudoknotted structures (extended abstract). Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.1037-1048, 2010, DMTCS Proceedings. 〈hal-01186262〉

Partager

Métriques

Consultations de la notice

210

Téléchargements de fichiers

85