Combinatorial RNA design: Designability and structure-approximating algorithm

In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem in which one must return an RNA sequence that admits a given secondary structure as its unique base pair maximizing structure. First, we fully characterize designable structures using restricted alphabets. Then, under a classic four-letter alphabet, we provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in Θ(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating version of the problem that allows to extend bands (stems). We provide a Θ(n) algorithm which, given a structure S avoiding two trivially non-designable motifs, transforms S into a designable structure by adding at most one base-pair to each of its stems, and returns a solution sequence.