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

Abstract

The design of multi-stable RNA molecules has important applications in\nbiology, medicine, and biotechnology. Synthetic design approaches profit\nstrongly from effective in-silico methods, which can tremendously impact their\ncost and feasibility. We revisit a central ingredient of most in-silico design\nmethods: the sampling of sequences for the design of multi-target structures,\npossibly including pseudoknots. For this task, we present the efficient, tree\ndecomposition-based algorithm. Our fixed parameter tractable approach is\nunderpinned by establishing the P-hardness of uniform sampling. Modeling the\nproblem as a constraint network, our program supports generic\nBoltzmann-weighted sampling for arbitrary additive RNA energy models; this\nenables the generation of RNA sequences meeting specific goals like expected\nfree energies or \\GCb-content. Finally, we empirically study general properties\nof the approach and generate biologically relevant multi-target\nBoltzmann-weighted designs for a common design benchmark. Generating seed\nsequences with our program, we demonstrate significant improvements over the\npreviously best multi-target sampling strategy (uniform sampling).Our software\nis freely available at: https://github.com/yannponty/RNARedPrint .\n