Fixed-parameter tractable sampling for RNA design with multiple target structures

Abstract : BACKGROUND: 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 substantially reduce the need for costly wet-lab experiments. RESULTS: We devise a novel approach to a central ingredient of most in-silico design methods: the generation of sequences that fold well into multiple target structures. Based on constraint networks, our approach supports generic Boltzmann-weighted sampling, which enables the positive design of RNA sequences with specific free energies (for each of multiple, possibly pseudoknotted, target structures) and GC-content. Moreover, we study general properties of our approach empirically and generate biologically relevant multi-target Boltzmann-weighted designs for an established design benchmark. Our results demonstrate the efficacy and feasibility of the method in practice as well as the benefits of Boltzmann sampling over the previously best multi-target sampling strategy-even for the case of negative design of multi-stable RNAs. Besides empirically studies, we finally justify the algorithmic details due to a fundamental theoretic result about multi-stable RNA design, namely the #P-hardness of the counting of designs. CONCLUSION: RNARedPrint introduces a novel, flexible, and effective approach to multi-target RNA design, which promises broad applicability and extensibility. Our free software is available at: https://github.com/yannponty/RNARedPrint Supplementary data are available online.
Document type :
Journal articles
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-02112888
Contributor : Yann Ponty <>
Submitted on : Saturday, June 22, 2019 - 12:06:40 PM
Last modification on : Monday, July 8, 2019 - 2:59:19 PM

Identifiers

Citation

Stefan Hammer, Wei Wang, Sebastian Will, Yann Ponty. Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinformatics, BioMed Central, 2019, 20 (1), pp.209. ⟨10.1186/s12859-019-2784-7⟩. ⟨hal-02112888⟩

Share

Metrics

Record views

108

Files downloads

304