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

Stefan Hammer (1) , Yann Ponty (2, 3) , Wei Wang (4) , Sebastian Will (1)

1 University of Vienna [Vienna]
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 AMIBIO - Algorithms and Models for Integrative BIOlogy
4 LRI - Laboratoire de Recherche en Informatique

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

Mots clés: Multi-target RNA Design; Counting Complexity; Boltzmann Sampling

Domaines: Bio-informatique [q-bio.QM]

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. ⟨hal-01631277v1⟩