A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms

Yann Ponty 1, 2, * Cédric Saule 1, 3, 4
* Auteur correspondant
1 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]
Abstract : We extend an hypergraph representation, introduced by Finkelstein and Roytberg, to unify dynamic programming algorithms in the context of RNA folding with pseudoknots. Classic applications of RNA dynamic programming energy minimization, partition function, base-pair probabilities\ldots) are reformulated within this framework, giving rise to very simple algorithms. This reformulation allows one to conceptually detach the conformation space/energy model -- captured by the hypergraph model -- from the specific application, assuming unambiguity of the decomposition. To ensure the latter property, we propose a new combinatorial methodology based on generating functions. We extend the set of generic applications by proposing an exact algorithm for extracting generalized moments in weighted distribution, generalizing a prior contribution by Miklos and al. Finally, we illustrate our full-fledged programme on three exemplary conformation spaces (secondary structures, Akutsu's simple type pseudoknots and kissing hairpins). This readily gives sets of algorithms that are either novel or have complexity comparable to classic implementations for minimization and Boltzmann ensemble applications of dynamic programming.
Type de document :
Communication dans un congrès
WABI - 11th Workshop on Algorithms in Bioinformatics - 2011, 2011, Saarbrucken, Germany. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00601060
Contributeur : Yann Ponty <>
Soumis le : dimanche 19 juin 2011 - 13:43:45
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08
Document(s) archivé(s) le : mardi 20 septembre 2011 - 02:20:29

Fichiers

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

Identifiants

  • HAL Id : inria-00601060, version 1
  • ARXIV : 1106.3771

Citation

Yann Ponty, Cédric Saule. A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms. WABI - 11th Workshop on Algorithms in Bioinformatics - 2011, 2011, Saarbrucken, Germany. 2011. 〈inria-00601060〉

Partager

Métriques

Consultations de la notice

320

Téléchargements de fichiers

351