A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms

Yann Ponty 1, 2, * Cédric Saule 1, 3, 4
* 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 : 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.
Complete list of metadatas

Cited literature [56 references]  Display  Hide  Download

Contributor : Yann Ponty <>
Submitted on : Sunday, June 19, 2011 - 1:43:45 PM
Last modification on : Wednesday, April 17, 2019 - 12:15:33 PM
Long-term archiving on : Tuesday, September 20, 2011 - 2:20:29 AM


Files produced by the author(s)


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



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



Record views


Files downloads