id: 05946461
dt: a
an: 05946461
au: Ponty, Yann; Saule, Cédric
ti: A combinatorial framework for designing (pseudoknotted) RNA algorithms.
so: Przytycka, Teresa M. (ed.) et al., Algorithms in bioinformatics. 11th
    international workshop, WABI 2011, Saarbrücken, Germany, September
    5‒7, 2011. Proceedings. Berlin: Springer (ISBN
    978-3-642-23037-0/pbk). Lecture Notes in Computer Science 6833. Lecture
    Notes in Bioinformatics, 250-269 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: RNA folding; Pseudoknots; Boltzmann Ensemble; Hypergraphs; Dynamic
    Programming
ci: 
li: doi:10.1007/978-3-642-23038-7_22
ab: Summary: 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$\cdots )$ 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.
rv: