Title: 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. Our fixed parameter tractable approach is
underpinned by establishing the P-hardness of uniform sampling. Modeling the
problem as a constraint network, our program 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 our program, we demonstrate significant improvements over the
previously best multi-target sampling strategy (uniform sampling).Our software
is freely available at: this https URL .