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 profit strongly from effective in-silico methods, which can tremendously impact their cost and feasibility. We revisit a central ingredient of most in-silico design methods: the sampling of sequences for the design of multi-target structures, possibly including pseudoknots. For this task, we present the efficient, tree decomposition-based algorithm \ourprog{}. Our fixed parameter tractable approach is underpinned by establishing the $\#${\sf P}-hardness of uniform sampling. Modeling the problem as a constraint network, \ourprog{} supports generic Boltzmann-weighted sampling for arbitrary additive RNA energy models; this enables the generation of RNA sequences meeting specific goals like expected free energies or \GCb-content. Finally, we empirically study general properties of the approach and generate biologically relevant multi-target Boltzmann-weighted designs for a common design benchmark. Generating seed sequences with \ourprog{}, we demonstrate significant improvements over the previously best multi-target sampling strategy (uniform sampling).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://recomb2018.fr〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01631277
Contributeur : Yann Ponty <>
Soumis le : samedi 31 mars 2018 - 12:18:59
Dernière modification le : jeudi 12 juillet 2018 - 12:56:35

Fichiers

RNARedPrint-Bioinfo2018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01631277, version 2
  • ARXIV : 1804.00841

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://recomb2018.fr〉. 〈hal-01631277v2〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

92