Ribonucleic Acid (RNA) plays essential roles in the core activities within living cells such as transcription and translation [6], catalyzing reactions [7], and controlling gene expression [18]. Given a target structure, RNA design aims to find sequences that can fold into that structure. This problem, however, has been proved NPhard [5] when the simplest model of energy is adopted. The importance of RNA structure and the hardness of RNA design problem have motivated various RNA design methods [3,4,8,10,13,16,17,19,24,25].
While extensive research has been dedicated to designing RNA based on a target structure, there is a notable scarcity of literature investigating the undesignability of RNA design using realistic energy models. Undesignability refers to the inability to find an RNA sequence that can fold into a desired structure using a realistic energy model. Initially, specific cases of undesignability were discovered by the work [1] attempting to extend RNA-SSD [3], which identified two undesignable motifs and proposed alternative motifs that would consistently be favored by the conventional Turner energy models [20]. Later work [9] has presented additional motifs that prevent designability, as observed using the maximum base pair model, which is not necessarily realistic. Recent works [23,22] outlined a method to verify undesignability for short motifs through exhaustive enumeration and folding. To the best of our knowledge, the examination of undesignable structures or motifs based on the nearest neighbor model [14,15,20] has not been thoroughly explored thus far.
To bridge the gap between RNA design and undesignability, we propose a systematic and scientifically grounded approach known as "Rival Structure Generation and Structure Decomposition" (RIGENDE). Our methodology operates on the principle of "proof by construction," whereby undesignability is confirmed by the identification of rival structures that consistently outperform the target structure for any possible RNA sequence. RIGENDE can not only serve as a sanity check for empirical RNA design methods, allowing for the avoidance of executing heuristic-based algorithms in situations where no feasible solution exists, but also provide deeper insights into the energy models themselves. This, in turn, contributes to a more profound understanding of thermodynamic models used for the prediction of RNA secondary structures. The main contributions of this paper are:
1. Theorems. We establish the theoretical grounds for Undesignable RNA Structure Identification, characterizing the importance of rival structure(s) and structure decomposition. 2. Algorithms. Driven by the proposed theorems, we designed and implemented highly e!cient algorithms to verify undesignability automatically. 3. Application. When applying to the puzzles from Eterna100 [2] benchmark, RIGENDE is able to prove 15 of them are undesignable. Remarkably, the verification process for each puzzle was completed within a matter of seconds or minutes.
2 RNA Design
2.1 Secondary Structure, Loop and Free Energy Stack Internal Loop Hairpin Hairpin Bulge Table 1: Critical positions of loops in Fig. 1 Loop Type
Table 2: Critical positions for each type of loops under Turner model implemented in ViennaRNA Special hairpins [15] of triloops, tetraloops and hexaloops are not considered here
An RNA sequence x of length n is specified as a string of base nucleotides x 1 x 2 . . . x n , where x i → {A, C, G, U} for i = 1, 2, ..., n. A secondary structure P for x is a set of paired indices where each pair (i, j) → P indicates two distinct bases x i x j → {CG, GC, AU, UA, GU, UG} and each index from 1 to n can only be paired once. A secondary structure is pseudoknot-free if there are no two pairs (i, j) → P and (k, l) → P such that i < k < j < l. In short, a pseudoknot-free secondary structure is a properly nested set of pairings in an RNA sequence. Alternatively, P can be represented as a string y = y 1 y 2 . . . y n , where a pair of indices (i, j) → P corresponds to y i = "(", y j = ")" and any unpaired index k corresponds to y k = ".". The unpaired indices in y are denoted as unpaired (y) and the set of paired indices in y is denoted as pairs(y), which is equal to P. In nature, some RNA structures contain crossing pairings called pseudoknots. Since the computational model we use does not allow these, we do not consider them. Henceforth we elide pseudoknot-free secondary structure to just secondary structure or structure for brevity.
The ensemble of an RNA sequence x is the set of all secondary structures that x can possibly fold into, denoted as Y(x). The free energy ωG(x, y) is used to characterize the stability of y → Y(x). The lower the free energy ωG(x, y), the more stable the secondary structure y for x. In the nearest neighbor energy model [20], a secondary structure is decomposed into a collection of loops, where each loop is usually a region enclosed by some base pair(s). Depending on the number of pairs on the boundary, main types of loops include hairpin loop, internal loop and multiloop, which are bounded by 1, 2 and 3 or more base pairs, respectively. In particular, the external loop is the most outside loop and is bounded by two ends (5 → and 3 → ) and other base pair(s). Thus each loop can be identified by a set of pairs. Fig. 1 showcases an example of secondary structure with various types of loops, where the some of the loops are notated as
1. Hairpin: H→(12, 18)↑. 2. Bulge: B→(10, 23), (11, 19)↑. 3. Stack: S→(3, 50), (4, 49)↑. 4. Internal Loop: I→(29, 43), (32, 39)↑. 5. Multiloop: M →(5, 48), (9, 24), (28, 44)↑. 6. External Loop: E→(3, 50)↑.
The function loops(y) is used to denote the set of loops in a structure y. The free energy of a secondary structure y is the sum of the free energy of each loop,
where each term ωG(x, z) is the energy for one specific loop in loops(y). See Supplementary Section B for detailed energy functions for di"erent types of loops in the Turner model implemented in ViennaRNA [13].
The energy of each loop is typically determined by nucleotides on the positions of enclosing pairs and their adjacent mismatch positions, which are named as critical positions in this article. Table 1 lists the critical positions for all the loops in Fig. 1 and Table 2 shows the indices of critical positions for each type of loops. Additionaly, some special hairpins [15] of unstable triloops and stable tetraloops and hexaloops in
Turner model have a separate energy lookup table (See Supplementary Section B.2). When evaluating the energy of a loop, it su!ces to input only the nucleotides on its critical positions, i.e., ωG(x, y) = z↑loops(y)
where critical (z) denotes the critical positions of loop z and x ↑ critical (z) denotes the nucleotides from x that are "projected" onto critical (z). See Supplementary Section A for the detailed functionality of projection operator. The projection (↑) allows us to focus on the relevant nucleotides for energy evaluation. For instance, critical (H→ (12,18)
critical (I→(29, 43), (32, 39)↑) = {29, 30, 31, 32, 39, 40, 42, 43}. (4) For convenience of later discussion, we also interchangeably put paired positions in brackets, i.e., critical (H→(12, 18)↑) = {(12, 18), 13, 17}, (5) critical (I→(29, 43), (32, 39)↑) = {(29, 43), (32, 39), 30, 31, 40, 42}. (6) 2.2 MFE and Structure Distance The structure with the minimum free energy is the most stable structure in the ensemble. A structure y ω is an MFE structure of x, i.e. MFE(x), if and only if ↓y → Y(x) and y ↔ = y ω , ωG(x, y ω ) ↗ ωG(x, y).
RNA design is the inverse problem of RNA folding. Given a target structure y ω , RNA design aims to find suitable RNA sequence x such that y ω is an MFE structure of x. For convenience, we define X (y) as the set of all RNA sequences whose ensemble contains y, i.e., X (y) = x | y → Y(x). Here we follow a more strict definition of MFE criterion adopted in some previous studies [5,9,23,21,25] on the designability of RNA, i.e., x is a correct design if and only if y is the only MFE structure of x, which we call unique MFE (uMFE) criterion to di"erentiate it from the traditional MFE criterion. Formally, uMFE(x) = y ω if and only if ↓y → Y(x) and y ↔ = y ω , ωG(x, y ω ) < ωG(x, y).
From the perspective of optimization, the satisfaction of MFE criterion requires that the structure distance between target structure y ω and MFE structure of x is minimized to 0. Therefore, many methods focus on optimizing d(y ω , MFE(x)). The function d(y → , y →→ ) represents the distance between two secondary structures y → and y →→ , which is defined as
where y → and y →→ have the same length
Based the uMFE criterion in Eq. 8, the straightforward meaning of undesignability is that such a condition can not be satisfied for any RNA sequence x given a target structure y ω . Alternatively, we give the formal definition of undesignability as follows.
Definition 1. An RNA secondary structure y ω is undesignable by uMFE criterion if and only if
Similarly, we have the definition of undesignability under MFE criterion.
Definition 2. An RNA secondary structure y ω is undesignable by MFE criterion if and only if
Following previous work [9] on undesignability, the discussions in this paper are under the setting of the uMFE criterion and Definition 1. However, all discussions can be straightforwardly adapted to Defition 2.
Given a target structure y ω of length n, the designed sequence x should have the same length. Therefore, the most straightforward method is to enumerate all RNA sequences of length n, and check whether there exist at least one RNA sequence that can fold into y ω . Considering the designed sequence should at least satisfy that nucleotides at the paired position of the target structure should be matchable, the number of bruteforce enumeration is 6 • n 3 ) makes brute-force search impractical even for very short structures.
One observation from RNA design is that when the designed RNA sequence x can not fold into the target structure y ω , sometimes x tends to fold into another structure y → . Another observation is that y → can be very close to y ω , i.e., their structure distance d(y ω , y → ), can be very small. For example, when designing the puzzle "Simple Single Bond" (shown as y ω in Fig. 2) from the benchmark Eterna100, the designed sequence (shown as x in Fig. 2) tends to fold into another similar structure (shown as y → in Fig. 2).
In this instance, we know that at least for x, y → is a more advantageous choice than y ω . We further hypothesize that y → is superior to y ω for any RNA sequence that can possibly fold fold into y ω . If the hypothesis holds, then we can assert that y ω is undesignable under uMFE criterion. This leads to the first theorem we proposed. Theorem 1. A structure y ω is undesignable, if
It is worth noting that the condition in Theorem 1 is a special case of the condition in Definition 1, despite both employing the same notations but in di"erent order. The correctness of Theorem 1 can be proven by the Definition 1. Whether the undesignability can be approached by Theorem 1 can be formulated as an optimization or feasibility problem.
If Theorem 1 can be applied, the problem of undesignability boils down to showing that y → is superior to y ω for any RNA sequence, we can rewrite the inequality in Eq. 12 as
Combining Eq. 2, Eq. 14 can be written as the di"erence of two sets of energy units, Table 3: Example of design constraint I 11 12 13 14 19 20 21 22 x1
The loops in loops(y → ) and loops(y ω ) are compared via the Venn diagram in Fig. 3. As we can see, the loops in y → and y ω overlap a lot. As a result, we can simplify Eq. 15 by canceling those intersected loops,
By Eq. 16, the energy di"erence does not necessarily involve each nucleotide of x. It is equivalent to consider only the nucleotides participating the calculation of energy di"erence in Equation 16, which can be written as
where
and
We name #(y → , y ω ) as di!erential positions as it is a set of all the positions whose nucleotides are involved in calculating the free energy di"erence between y → and y ω . Accordingly, each nucleotide of x corresponds to one position in #(y → , y ω ), and the number of nucleotides in x is the same as the size of #(y → , y ω ). Eq. 17 implies that enumerating all possible (x is equivalent to enumerating all possible x. Suppose the number of paired positions and unpaired positions in #(y → , y ω ) are p and q, the total number of enumeration would be p 6 ⇒ q 4 . Moreover, the time cost of evaluating Eq. 19 is almost O(1) as loops(y → ) and loops(y ω ) only need to be computed once. As a result, it would be not hard to determine whether y → satisfies Theorem 1 when
, y ω )| is small, which motivates our first algorithm to e!ciently verify undesignability, as described in Algorithm 1. In the case of example in Fig. 2, #(y → , y ω ) = {(7, 39), (17, 29), 6, 8, 16, 30, 38, 40}, total number of enumerations of x in Eq. 17 is 147456 which can be finished within 1 second on a single computer in our experiments. To give a specific complexity, X !(y → ,y ω ) is used to denote the all possible nucleotide compositions at the positions in D(y → , y ω ), we have
To prevent excessive runtime, our implementation selects only y → that is su!ciently close to y ω as input to Algorithm 1, specifically when X ω(y → ,y ) > M, where M is a large integer.
Input : y ω , y → ; // y → = MFE(x), x comes from RNA Design Output : (I, X); // X will store all the x that violates Theorem 1
In fact, if y → is always superior to y ω , any sequence x → X (y ω ) must be able to fold into y → , which leads to the following corollary.
Corollary 1. If y → satisfies the condition in Theorem 1, then we have pairs(y → ) ⇑ pairs(y ω ).
Proof. Suppose there exists a pair (i, j) such that (i, j) → pairs(y → ) but (i, j) / → pairs(y ω ). For any sequence x where x i x j is not among the allowed base pairs, i.e. x i x j / → {CG, GC, AU, UA, GU, UG}, x cannot fold into y → because ωG(x, y → ) = ⇓. Therefore, if x prefers y → to y ω , then y → cannot have any pair (i, j) not in pairs(y ω ). Since y → ↔ = y ω , it follows that pairs(y → ) ⇑ pairs(y ω ).
While Algorithm 1 is e"ective in verifying the potential rival structure y → , it is important to acknowledge that an arbitrary structure y → does not necessarily always have a lower free energy than the target structure y ω . Generally, the entire search space consisting of all possible RNA sequences can be divided into two subsets depending on whether each sequence x prefers y ω to y → .
X (y ? ∏ y 0 1 ) X (y ? ∏ y 0 2 ) X (y ? ) Fig. 4: Undesignability proven by 2 rival structures, X (y ω ⇔ y →1 ) X (y ω ⇔ y →2 ) = X (y ω ) Proposition 1. Given a target structure y ω and another structure y → ↔ = y ω , the RNA design space X (y ω ) can be divided into the two sets below.
Following Proposition 1, the feasibility problem in Eq. 13 is equivalent to
In cases when no feasible y → satisfiying Eq. 21 can be found, we consider extending Theorem 1 and feasibility problem 21 to multiple rival structures identification.
Theorem 2 can also be proven by the Definition 1. The corresponding optimization formulation is find Y = {y →1 , y →2 , .., y →k } subject to
Fig. 4 shows a venn diagram when we can prove undesignability by finding a set of 2 rivial structures
for any sequence x → X (y ω ), either y →1 or y →2 would have lower free energy than y ω .
Given input y ω and y → , we call the output of Algorithm 1 a design constraint, which characterizes the set X (y ω < y → ). For example, Fig. 5 contains a target structure y ω from Eterna puzzle "Zigzag Semicircle", along with a designed sequence x and y → = MFE(x). Upon applying Algorithm 1, the output is a tuple consisting of I = #(y → , y ω ) = { (11,22), (12,20), 13, (14, 19), 21} and a set X = {x 1 , x2 , .., x90 }. Table 3 displays 5 nucleotides compositions in X. The functionality of Algorithm 1 ensures that any sequence x → X (y ω < y → ) must satisfy the design constraint (I, X) and any sequence satisfying the design constraint (I, X) is in
As a result, we can use (I, X) to represent the set X (y ω < y → ) and conduct set operations such as intersection and union. A high level algorithm for solving Eq. 22 is shown in Algorithm 2. Starting from a seed x and y → = MFE(x), Algrithm 2 repeatedly calls Algorithm 1 to get new potential y → and corresponding design constraint
Algorithm 2: Identify Multiple Rival Structures Input : y ω , x ; // x come from (unsuccessful) RNA design Output : undesignable/designable/unknown 1 X ↑ X(y ω ); // Design (search) space for y ω 2 Y ↑ ⊋; // Contains all potential rival structures y → 3 Q ↑ {x}; // A queue contains RNA sequences for folding 4 while Q is not empty do 5 x ↑ pop(Q); 6 if uMFE(x) = y ω then 7 return designable; // Identify designable case 8 y → = MFE(x); 9 if y → ↓ Y then break; // Stop if no new y → 10 if | X !(y → ,y ω ) | > M then // Continue if too many enumeration in Algorithm 1 11 continue 12 X (y ω < y → ) ↑ Algorithm 1(y ω , y → ); 13 X ↑ X ↘ X(y ω < y → ) ; // Set intersection 14 Y ↑ Y ↗ {y → }; 15 if X = ⊋ then return undesignable; 16 if |Y | > N then break; // Stop if Y is too large 17 if Q is empty then 18 for i = 1 to K do // Sample at most K sequences 19 Sample xnew ↓ X ; 20 Q ↑ push(Q, xnew); 21 return unknown X (y ω
< y → ). Each new design constraint is intersected (line 13) with all the other design constraints previously found. An example of design constraint intersection is show in Table 4. Refer to Supplementary Section A for specific steps of constraint intersection. The algorithm stops if no new rival structure candidate can be found or there are too many rival structures in Y . Algorithm 2 has 3 parameters: (1) M is the maximum enumeration allowed for Algorithm 1; (2) N is maximum number of rival structures allowed in Y ; (3) K is the number of sampled sequences from design space X . At most N set intersections are executed, and at most NK sequences are sampled and folded. Assuming hash sets are used, the time complexity of set intersection is O(M ). Therefore, the overall complexity of Algorithm 2 is O(NM + NKn 3 ), where n is the length of the input target structure.
While Algorithm 1 and 2 are e!cient when the input #(y ω , MFE(x)) is small, it is not practical otherwise. For instance, Fig. 6 showcases the puzzle "multilooping fun" from Eterna100 benchmark. The di"erence between y ω and y → is so huge that is not suitable as input for Algorithm 1 and 2. It is worth noting that a base pair (i, j) → y ω divides the free energy ωG(x, y ω ) into two uncoupled parts: one within and one outside
When it is impractical to apply Algorithm 1 and 2 to the entire structure y ω , it might be beneficial to search for rival structures for a pair-bounded substructure y ω i↔j . For example, if another pair-bounded y →→ i↔j is always more advantageous, then replacing y ω i↔j with y →→ i↔j in y ω will yield another structure y →→ that qualifies as a rival structure for y ω . However, the crucial point for such a decomposition and combination is that both y ω i↔j and y →→ i↔j must be enclosed by a pair, ensuring that the free energy is the sum of the energy of loops within the pair and outside the pair (i, j). Therefore, we propose to decompose a target structure by base pairs such that the undesignability of a pair-bounded substructure can assure the undesignability of the original target structure. Definition 3. A structure y = y 1 y 2 . . . y n is context-constrained if (1, n) → pairs(y), i.e., its first and last positions are paired.
For a sequence x = x 1 x 2 . . .
A context-constrained structure y ω is the context-constrained uMFE structure of x, i.e., uMFE CC (x), if and only if ↓y → Y CC (x) and y ↔ = y ω , then ωG(x, y ω ) < ωG(x, y).
Accordingly, we can define context-constrained undesignability by uMFE criterion.
Definition 4. A context-constrained structure y ω is context-constrained-undesignable if and only if ↓x → X (y ω ), ⇐y → ↔ = y ω and y → is context-constrained, ωG(x, y → ) ↗ ωG(x, y ω ).
The above definitions allow us to succinctly express the idea of proving undesignability via structure decomposition in Theorem 3. Theorem 3. A structure y ω is undesignable if there exists a pair (i, j) → pairs(y ω ) such that the structure y ω i↔j is context-constrained undesignable, where y ω i↔j = y ω i y ω i+1 . . . y ω j . Proof. By Def. 4, ↓x i↔j → X (y ω i↔j ), ⇐y → i↔j ↔ = y ω i↔j and y → i↔j is context-constrained, ωG(x i↔j , y → i↔j ) ↗ ωG(x i↔j , y ω i↔j ). We can construct a structure y →→ ↔ = y ω by substituting y ω i↔j within y ω with y → i↔j such that loops(y →→ ) = loops(y ω ) \ loops(y ω i↔j ) ↙ loops(y → i↔j ). As a result, ↓x → X (y ω ),
The algorithm for Theorem 3 is presented in Algorithm 3. Each substructure of the target structure bounded by a pair (i, j) can be regarded as a context-constrained structure, which is input to Algorithm 2. For e!ciency we excluded those pairs enclosing a hairpin loop or a stack loop. The target structure is then proven undesignable if one decomposed substructure is verified to be context-constrained undesignable. Since Algorithm 2 is called at most n/2 times, the overall complexity of Algorithm 3 is O(NMn + NKn 4 ).
Algorithm 3: Identify Rival Structures with Structure Decomposition Input : y ω , x ; // x comes from RNA Design Output : undesignable/unknown 1 foreach (i, j) ↓ pairs(y ω ) do 2 if H→(i, j)↑ / ↓ loops(y ω ) and S→(i, j), (i + 1, j → 1)↑ / ↓ loops(y ω ) then // Hairpin&stack excluded 3 if y ω i↑j ≃ = uMFECC(xi↑j) then // Constrained folding 4 if Algorithm2(y ω i↑j , xi↑j) = undesignable then // Use MFECC&uMFECC in Alg.2 5 return undesignable 6 return unknown;
5 Experiments on Eterna100 Dataset
We applied the three algorithms described in Section 4 to structures from the Eterna100 dataset [2], a well-known benchmark for RNA inverse folding. Eterna100 contains a list of 100 secondary structure design challenges (also called puzzles) with a wide range of di!culties.
A previous study [12] identified 19 puzzles were never successfully designed with the folding parameters of ViennaRNA 2.5.1. We took a step further and tried to prove that it is impossible to solve some of Eterna100 puzzles under the uMFE criterion.
For each target structure y ω in Eterna100, we first attempted RNA design using two state-of-the-art methods NEMO [16] and SAMFEO [25]. We chose the two because our previous studies show that they were able to solve the most puzzles [25]. We adopted the same setting as the RNA design experiments in SAMFEO [25]. Eventually, we obtained 22 structures that neither of the two programs designed successfully under the uMFE criterion with ViennaRNA 2.5.1 parameters. For each unsolved puzzle y ω , we selected the output x such that its MFE structure y → has the minimal structure distance d(y ω , y → ), then we used y ω , y → , and x as the input to our algorithms.
The three algorithms are implemented in C++ and running on Linux, with 3.40 GHz Intel Xeon E3-1231 CPU and 32G memory. Our implementation also utilized OpenMP to achieve parallelization and the program was ran with 8 CPUs. In Algorithm 2, we used LinearFold [11] (beam size set as 0, which means exact search without beam pruning) with the energy parameter from ViennaRNA 2.5.1 to find MFE(x) and uMFE(x). LinearFold also provides the functionality for constraint folding, which is used in Algorithm 3 to obtain MFE CC (x i↔j ) and uMFE CC (x i↔j ). Notice our algorithms do not rely on any specific folding package, our released implementation also support using ViennaRAN package for folding and constrained folding which will yield the same output. To prevent the algorithms from running indefinitely, we set the parameters in Algorithm 2 as follows: M = 10 10 , N = 10 5 , K = 500.
The results of applying our algorithms are presented in Table 5. In total, we identified that 15 out of those the 22 puzzles are undesignable using ViennaRNA 2.5.1 parameters. The algorithms identified the rival structure(s) for 14 out of those 15 undesignable puzzles automatically. For the Puzzle 87, the algorithms took the puzzle and a candidate rival (sub)structure we manually selected then proved the puzzle is undesignable according to Theorem 3. The implementation of our algorithm also enable turning o" special hairpins in energy model. As a result, in addition to the aforementioned 15 undesignable puzzles, our algorithms can automatically prove the Puzzle 50 is undesignable when special hairpins are not considered.
An additional noteworthy finding is that Algorithm 2 can also identify a uMFE (or MFE) solution (line 7) in the process of searching rival structure candidates by folding new sequences. Remarkably, the puzzle "Short String 4" (in the 22 unsolved puzzles) turned out to be designable, i.e., Algorithm 2 successfully generated an RNA sequence that adopts the target structure as the unique MFE structure. See Supplementary Section C for the structure of "Short String 4" along with the designed sequence. Finally, the designability of remaining 5 puzzles remains uncertain, whose puzzles names are Taraxacum officinale, Mat-Lot2-2B, Gladius, Hoglafractal, and Teslagon.
For those puzzles proven undesignable by our three algorithms, we further compared the identified rival structuresfoot_1 with original target structures. Main insights are summarized as follows.
1. The undesignability identified by Algorithm 1 is usually caused by some lonely pair or double pairs in the target structure, which is consistent to the observation of previous study [2] on the di!culty of puzzles. For example, the y → in Fig. 2 has one less pair compared to y ω . However, our approach can provide loop-level reasoning and quantitative explanation, which goes beyond heuristics. 2. However, contrary to the principle [2] that symmetry is a feature of di!culty for RNA design, we found that the undesignability is usually caused by some independent local region in a target structures, as is highlighted in the structures plot in Table 5. 3. If an undesignable structure can be proven by identifying multiple rival structures, the number of the rivals tends to be small and those rival structures can be very similar to each other. There are 4 cases with multiple rival structures in Table 5, and their number of rivial structures are 8, 9, 9, 2 respectively. 4. The constrained-context undesignable structures identified by Algorithm 3 often contains some hairpin enclosed by a single pair or double pairs as the cases highlighted in Table 5. However, it is hard to locate those regions by attempting RNA design and find a y → similar to target structure y ω , which demonstrates the cruciality of structure decomposition.
Following the core idea of proof by construction, we propose three e!cient and explainable algorithms (RIGENDE) for proving undesignability in the context of RNA design with the nearest neighbor model. Theoretically, the theorems we introduced can shed some light on why and how some structures are not designable. The establishment of those concepts such as rival structure, designability constraint, and context-constrained undesignability can be regarded as a milestone for automatically verifying undesignability. Applied to Eterna100 benchmark, RIGENDE can prove 15 of them are actually undesignable using popular Turner model implemented in ViennaRNA 2.5.1 and LinearFold. Without doubt, the found rival structures can help humans understand more about RNA folding and RNA design. The main drawbacks of RIGENDE include:
1. The rival structure candidates are crucial for the algorithms to work, and the selection of candidates is dependent on the results of RNA design. 2. The structure decomposition in Algorithm 3 only considers a pair-bounded substructure, which may not be able to cover other sophisticated cases.
In the future, we would address those drawbacks. We will not only prove more cases of undesignability on structure level but also examine the undesignability on the level of structure motifs.
1. Design better ways to find rival structure candidates, such as devising approaches that eliminate the necessity of relying on external RNA design methods. 2. Decompose structures according to the topology of loops instead of splitting the entire structure into two via a base pair. 3. Experiment with more puzzles and RNA design settings to search for more general regularities of designability and undesignability. Table SI 1: List of special hairpins in the Turner energy model. x "G special hairpin (x, (...)) CAACG 6.8 GUUAC 6.9 x "G special hairpin (x, (....)) CAACGG 5.5 CCAAGG 3.3 CCACGG 3.7 CCCAGG 3.4 CCGAGG 3.5 CCGCGG 3.6 CCUAGG 3.7 CCUCGG 2.5 CUAAGG 3.6 CUACGG 2.8 CUCAGG 3.7 CUCCGG 2.7 CUGCGG 2.8 CUUAGG 3.5 CUUCGG 3.7 x "G special hairpin (x, (......)) ACAGUACU 2.8 ACAGUGCU 2.9 ACAGUGAU 3.6 ACAGUUCU 1.8 B.4 Bulge Set length = k ↘ i + j ↘ l ↘ 2.
ω In Proceedings of RECOMB 2024, Lecture Notes in Computer Science (LNCS 14758), pp. 270-287, Springer.
We released those rival structures at https://github.com/shanry/RNA-Undesign/tree/main/data/results/rigend.
This puzzle is proven undesignable if we ignore energies of special hairpins.