Search for: All records

RNA design aims to find a sequence that folds with the highest probability into a designated target structure. However, certain structures are undesignable, meaning no sequence can fold into the target structure under the default (Turner) RNA folding model. Understanding the specific local structures (i.e., “motifs”) that contribute to undesignability is crucial for refining RNA folding models and determining the limits of RNA designability. Despite its importance, this problem has received very little attention, and previous efforts are neither scalable nor interpretable. We develop a new theoretical framework for motif (un-)designability, and design scalable and interpretable algorithms to identify minimal undesignable motifs within a given RNA secondary structure. Our approach establishes motif undesignability by searching for rival motifs, rather than exhaustively enumerating all (partial) sequences that could potentially fold into the motif. Furthermore, we exploit rotational invariance in RNA structures to detect, group and reuse equivalent motifs and to construct a database of unique minimal undesignable motifs. To achieve that, we propose a loop-pair graph representation for motifs and a recursive graph isomorphism algorithm for motif equivalence. Our algorithms successfully identify 24 unique minimal undesignable motifs among 18 undesignable puzzles from the Eterna100 benchmark. Surprisingly, we also find over 350 unique minimal undesignable motifs and 663 undesignable native structures in the ArchiveII dataset, drawn from a diverse set of RNA families. 

RNA design aims to find a sequence that can fold into a given (secondary) structure, which has wide applications in science and medicine. However, it has long been known that there are “undesignable structures” for which no sequence can fold into them according to the minimum free energy (MFE) criterion under the standard RNA folding energy model. Our previous work showed that undesignable structures can be effectively and efficiently identified by searching for rival structures. We further showed that there exist “minimal undesignable motifs” within those undesignable structures, where a (structural) motif is a set of consecutive loops and helices within a secondary structure. To better illustrate our theoretical findings, we built a motif server as a user-friendly visualization tool for undesignable RNA structures and motifs, as well as an interactive demo tool where the user can input a new structure and the server will compute and visualize any undesignable motifs within it on the fly. This server maintains a database of undesignable RNA structures and unique minimal undesignable RNA motifs, allowing the users to explore, visualize, analyze, and identify undesignable motifs in existing and new RNA structures. The importance of this server is that it provides a database of motifs for nanostructure design that should not be incorporated because these motifs are unlikely to be achievable. Availability: Our server is at https://linearfold.eecs.oregonstate.edu/motifserver. 

RNA design aims to find a sequence that folds into a designated target structure under a specific RNA folding model, also known as the inverse problem of RNA folding. While numerous RNA design methods have been invented to search for sequences capable of folding into a target structure under the default (Turner) RNA folding model, little attention has been given to the identification of undesignable structures. This work bridges the gap between RNA design and undesignability by introducing a series of theorems and algorithms aimed at identifying both undesignable structures and their causative local structural components, which we define asminimal undesignable motifs. We first present theorems that provide sufficient conditions for recognizing undesignability structures and propose efficient, theorem-guided algorithms to verify whether an RNA structure is undesignable. While such global undesignability sheds light on the limits of RNA design, identifying the specific motifs responsible for undesignability is critical for understanding RNA folding models and advancing design methodologies. To this end, we develop a new theoretical framework for motif undesignability and propose scalable and interpretable algorithms to identify minimal undesignable motifs within a given RNA secondary structure. Our approach establishes motif undesignability by searching for rival motifs, rather than exhaustively enumerating all (partial) sequences that could potentially fold into the motif. Furthermore, we exploit rotational invariance in RNA structures to detect, group, and reuse equivalent motifs and to construct a database of unique minimal undesignable motifs. To achieve that, we propose a loop-pair graph representation for motifs and a recursive graph isomorphism algorithm for motif equivalence. Our algorithms successfully identified 24 unique minimal undesignable motifs among 18 undesignable puzzles from the Eterna100 benchmark. Surprisingly, we also find over 350 unique minimal undesignable motifs and 663 undesignable native structures in the ArchiveII dataset, drawn from a diverse set of RNA families. Last but not least, we demonstrate that our theory and algorithms can handle motifs with external loops—a critical advancement given the substantial impact of external loops on the quantity, diversity, and designability of RNA structure motifs. 

RNA design aims to find a sequence that folds with the highest probability into a designated target structure. However, certain structures are undesignable, meaning no sequence can fold into the target structure under the default (Turner) RNA folding model. Understanding the specific local structures (i.e., “motifs”) that contribute to undesignability is crucial for refining RNA folding models and determining the limits of RNA designability. Despite its importance, this problem has received very little attention, and previous efforts are neither scalable nor interpretable. We develop a new theoretical framework for motif (un-)designability, and design scalable and interpretable algorithms to identify minimal undesignable motifs within a given RNA secondary structure. Our approach establishes motif undesignability by searching for rival motifs, rather than exhaustively enumerating all (partial) sequences that could potentially fold into the motif. Furthermore, we exploit rotational invariance in RNA structures to detect, group and reuse equivalent motifs and to construct a database of unique minimal undesignable motifs. To achieve that, we propose a loop-pair graph representation for motifs and a recursive graph isomorphism algorithm for motif equivalence. Our algorithms successfully identify 24 unique minimal undesignable motifs among 18 undesignable puzzles from the Eterna100 benchmark. Surprisingly, we also find over 350 unique minimal undesignable motifs and 663 undesignable native structures in the ArchiveII dataset, drawn from a diverse set of RNA families. 

RNA design aims to find a sequence that folds with the highest probability into a designated target structure. However, certain structures are undesignable, meaning no sequence can fold into the target structure under the default (Turner) RNA folding model. Understanding the specific local structures (i.e., “motifs”) that contribute to undesignability is crucial for refining RNA folding models and determining the limits of RNA designability. Despite its importance, this problem has received very little attention, and previous efforts are neither scalable nor interpretable. We develop a new theoretical framework for motif (un-)designability, and design scalable and interpretable algorithms to identify minimal undesignable motifs within a given RNA secondary structure. Our approach establishes motif undesignability by searching for rival motifs, rather than exhaustively enumerating all (partial) sequences that could potentially fold into the motif. Furthermore, we exploit rotational invariance in RNA structures to detect, group and reuse equivalent motifs and to construct a database of unique minimal undesignable motifs. To achieve that, we propose a loop-pair graph representation for motifs and a recursive graph isomorphism algorithm for motif equivalence. Our algorithms successfully identify 24 unique minimal undesignable motifs among 18 undesignable puzzles from the Eterna100 benchmark. Surprisingly, we also find over 350 unique minimal undesignable motifs and 663 undesignable native structures in the ArchiveII dataset, drawn from a diverse set of RNA families.