Skip to Main content Skip to Navigation
New interface
Journal articles

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: Supplementary data are available online.
Document type :
Journal articles
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download
Contributor : Yann Ponty Connect in order to contact the contributor
Submitted on : Saturday, June 22, 2019 - 12:06:40 PM
Last modification on : Saturday, June 25, 2022 - 9:12:43 PM




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



Record views


Files downloads