Fixed-Parameter Tractable Sampling for RNA Design with Multiple Target Structures

Abstract : The design of multi-stable RNA molecules has important applications in biology, medicine, and biotechnology. Synthetic design approaches largely benefit from effective in-silico methods, which can tremendously impact their cost and feasibility. Here, we revisit a central ingredient of most in-silico design methods: the sampling of sequences for multi-target design. We establish the #P-hardness of uniform sampling, and introduce RNARedPrint, a tree decomposition-based algorithm for efficient, fixed parameter tractable sampling. By modeling the problem as a constraint network, RNARedPrint supports generic Boltzmann-weighted sampling for arbitrary additive RNA energy models; this enables generating designs meeting specific goals like expected free energies or GC-content. Finally, we empirically study general properties of the approach and generate biologically relevant multi-target Boltzmann-weighted designs for a common design benchmark. In particular, we show significant improvements over seed sequences generated by uniform sampling, the previously best available sampling strategy for multi-target design. Our software is freely available at: https://github.com/yannponty/RNARedPrint
Type de document :
Communication dans un congrès
RECOMB 2018 – 22nd Annual International Conference on Research in Computational Molecular Biology, Apr 2018, Paris, France. 2018, 〈http://recm2018.fr〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01631277
Contributeur : Yann Ponty <>
Soumis le : jeudi 9 novembre 2017 - 01:03:58
Dernière modification le : lundi 22 janvier 2018 - 16:58:24

Fichier

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

Identifiants

  • HAL Id : hal-01631277, version 1

Citation

Stefan Hammer, Yann Ponty, Wei Wang, Sebastian Will. Fixed-Parameter Tractable Sampling for RNA Design with Multiple Target Structures. RECOMB 2018 – 22nd Annual International Conference on Research in Computational Molecular Biology, Apr 2018, Paris, France. 2018, 〈http://recm2018.fr〉. 〈hal-01631277〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

62