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 com- plete 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 gener- ation 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 ad es- ignable structure by adding at most one base-pair to each of its stems, and returns a solution sequence.
['Jozef Haleš', 'Ján Maňuch', 'Yann Ponty', 'Ladislav Stacho']
Combinatorial RNA Design: Designability and Structure-Approximating Algorithm