1 Introduction 5! 3! 5! 3!

Fig. 1: Going beyond structure undesignability in our previous work [35], this work finds minimal undesignable motifs in a given RNA structure (two such motifs shown here in Eterna100 puzzle #52). Boundary and internal pairs are in orange and blue, resp.

RNA design [34,4,22,12,32] focuses on identifying one or more RNA sequences capable of folding into a target secondary structure, holding significant promise for applications in RNA-based therapeutics and diagnostics [33].

The significance and complexity of RNA design have garnered widespread attention. Numerous methods, including SAMFEO [34], NEMO [22], RNAiFold [12], NUPACK [32], and others [4], have been developed to generate sequences based on a given target structure. Despite substantial improvements in empirical design quality, it has been noted that certain puzzles in the widely-used benchmark Eterna100 [2] are considered undesignable, having never been successfully solved [17]. However, limited research [1] has been dedicated to exploring the undesignability of RNA structures. Recently, We introduced RIGEND [35] to identify undesignable RNA structures in a more general manner by pinpointing rival structures, resulting in the identification of 16 puzzles in Eterna100 deemed undesignable by the unique minimum free energy (MFE) criterion under the standard Turner RNA folding model [21,26] implemented in ViennaRNA [20] .

While e!ective, RIGEND has some limitations in terms of explainability and scalability. While rival structures, which consistently exhibit better folding energy compared to the target structure, can serve as compelling evidence for an undesignable structure, their interpretability is often limited to the entire structure. In practice, the undesignability of an RNA structure typically arises from some specific local region, or structure motif. Identifying these critical motif(s) in a structure could o!er deeper insight into why certain structures resist design, enhancing both interpretability and potential reusability in RNA Design. Table 1: Critical positions of some loops in Fig. 2.

Loop Critical Positions Hairpin→ (12,18)↑ (12,18), 13, 17 Bulge→ (10,23), (11,19)↑ (10,23), (11,19) Stack→ (3,50), (4,49)↑ (3,50), (4, 49) Internal→ (29,43), (32,39)↑ (29,43), (32,39), 30,42,31,40 External→(3, 50)↑ (3, 50), 2, 51 . . . . . . 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. 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. While some RNA structures in nature contain pseudoknots, we do not consider them in this work as the computational model we use does not allow these. 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 [26], 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, the 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. 2 showcases an example of secondary structure with loops, and some of the loops are listed in Table 1.

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, #G → (x, y) = z↓loops(y) #G → (x, z), where each term #G → (x, z) is the energy for one specific loop in loops(y). See Supplementary Section G for detailed energy functions for types of loops in the Turner model [26]. The energy of each loop is typically determined by the identity of nucleotides on the positions of enclosing pairs and their adjacent mismatch positions, which are named as critical positions in this article. Table SI 1 lists the critical positions for all the loops in Fig. 2 and Table SI 2 shows the indices of critical positions for each type of loops. Additionally, some special hairpins [21] of unstable triloops and stable tetraloops and hexaloops in Turner model have a separate energy lookup table (See Supplementary Section G.2). When evaluating the energy of a loop, it su"ces to input only the nucleotides on its critical positions, i.e.,

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 B for the detailed functionality of projection operator. The projection (↑) allows us to focus on the relevant nucleotides for energy evaluation. Table 1 list the critical positions for the example loops.

The structure with the minimum free energy is the most stable structure in the ensemble. A structure y ω is an MFE structure of x if and only if

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. Here we follow a more strict definition of MFE criterion adopted in some previous studies [6,14,31,27,34] 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).

(3) Following previous work [14,35] on undesignability, we define the undesignability based the uMFE criterion, i.e., the condition in Eq.3 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 ↓x, ↘y

3 Motif and its Undesignability

Recent work, RIGEND [35], has demonstrated that some structures (puzzles) in Eterna100 are undesignable. For instance, the puzzle "[RNA] Repetitive Seqs. 8/10" in Fig. 1 is proven undesignable because there exists a rival structures always better a lower free energy than the target structure . However, this level of explainability remains at the global structure level rather than more specific local regions. Ideally, a solution should not only verify that a structure is undesignable but also pinpoint local regions as small as possible within structures that causes the undesignability. We refer to these regions as undesignable motifs.

Smaller undesignable motifs are easier to be resused to detect undesignability in structures. Thus, the goal is to identify minimal undesignable motifs from structures. For example, our proposed algorithm identified two minimal undesignable motifs in the puzzle "[RNA] Repetitive Seqs. 8/10", highlighted in Fig. 1. Previous e!orts [31,30] of exhaustive search fails at them due to scalability and deficit of motif definition.

We argue that the most e!ective way to define a motif is by focusing on the composition of loops, aligning with how RNA structures are composed of di!erent loop types (Section 2). In this way, a motif is regarded a full generalization of RNA structure. Our formal definition of motifs is introduced in the following subsection. Many functions defined for secondary structures can also be applied to motifs. For example, loops(m) represents the set of loops within a motif m, while pairs(m) and unpaired (m) represent the sets of base pairs and unpaired positions, respectively. We define the cardinality of m as the number of loops in m, i.e., card (m) = |loops(m)|. Fig. 3 illustrates three motifs, m 1 , m 2 , and m 3 , in a structure adapted from the Eterna puzzle "Cat's Toy". These motifs contain 1, 2, and 3 loops, respectively. We also define the length of a motif |m| as the number of bases it contains, which is consistent with the length of a secondary structure |y|.

Since motifs are defined as sets of loops, we can conveniently use set relations to describe their interactions. A motif m A is a sub-motif of another motif m B if m A is contained within m B , denoted as m A ≃ m B . For the motifs in Fig. 3, we observe the relation

The entire structure y can be regarded as the largest motif within itself, and accordingly, m ≃ y signifies that motif m is a part of structure y, with m ⇐ y implying m is strictly smaller than y.

The loops in a motif m are connected by base pairs. Each base pair in pairs(m) is classified as either an internal pair linking two loops in m or a boundary pair connecting one loop inside m to one outside. These two types of pairs in m are denoted as disjoint sets ipairs(m) and bpairs(m), respectively:

Utilizing the commonly accepted nearest neighbor model for RNA folding, it becomes evident that certain motifs may be absent from structures folded from RNA sequences. For instance, motif m 3 in Fig. 3 is considered undesignable, as the removal of its two internal pairs consistently reduces the free energy. This brings us to the definition of an undesignable motif.

The designability of motifs is based on constrained folding. Given a sequence x, a structure in its ensemble y → Y(x), we can conduct constrained folding by constraining the loops outside m, i.e., c = y \ m. We generalize the concept of (structure) ensemble to motif ensemble as the set of motifs that x can possibly fold into given the constraint c, denoted as M(x, c). Motifs in M(x, y \ m) have the same boundary pairs, i.e.,

The free energy of a motif m is the sum of the free energy of the loops in m,

The definitions of MFE and uMFE can also be generalized to motifs via constrained folding.

The designability and undesignability of motifs by uMFE criterion can be defined based on Def. 4.

Similarly, we can establish the definition of designable motifs.

Moreover, if m is undesignable, any motif or structure containing m will be undesignable.

We can construct a motif m ↑↑ ↔ = m by substituting the loops of m ω within m with m ↑↑ such that loops(m

Corollary 1. If a motif m ω is undesignable, then any structure y such that m ω ≃ y is also undesignable.

Proof. The structure y is the largest motif in y. Thus the correctness of Corollary 1 follows Theorem 1.

Corollary 2. If a motif m is designable, then any sub-motif m sub ⇐ m is also designable. As a special case, if a structure y is designable, then any motif m within y, i.e., m ⇐ y is also designable.

Proof. This follows as the contrapositive of Theorem 1, thus completing the proof.

According to Theorem 1, we can access the undesignability of a big motif by inspecting its sub-motifs. Therefore, it is crucial and valuable to determine the minimality of an undesignable motif. We introduce the concept of minimal undesignable motif. Definition 7. A motif m is a minimal undesignable motif if and only if the two conditions both hold: (1) m is an undesignable motif, and (2) ↓m ↑ ⇐ m, m ↑ is designable.

By this definition, the motif m 3 in Fig. 3 is a minimal undesignable motif because all its proper submotifs are designable. Since the minimality is based on the concept of loops, one fundamental question is that what's the least number of loops a minimal undesignable motif can contain. Therefore, it is worthwhile to prove that any motif composed of a single loop is designable.

Theorem 2. If a motif m ω is composed of one loop, i.e., card (m ω ) = 1, then m ω is designable.

Proof is detailed in Supplementary Section F.2. It turns out that it is possible for a two-loop motif to be minimal undesignable (as illustrated in Table 3). The primary issue is how to identify undesignable motifs. A trivial solution is to enumerate all the (partial) sequences for the target motif m ω and check the when m ω is a uMFE motif after constrained folding. However, it is impractical for long motifs because of exponentially high time cost. See Supplementary Section D for a detailed discussion. The existing work CountingDesign [31,30] is better than exhaustively enumerating sequences for each motif one by one, yet in essence it is still an exhaustive enumeration method. As a result, it cannot scale to long motifs and the found undesignable motifs lack interpretability. To provide scalability but also interpretability, we borrow the philosophy of rival structure from RIGEND [35] and propose to utilize rival motif to establish the undesignability of motifs, which is discussed in the following Section 4.

It is possible that there is another motif m ↑ which always has lower free energy than the target motif m ω , if we can find such a rival motif, m ω is undesignable. For instance, removing the internal pairs of the motif m 3 highlighted in Fig. 3 will yield a rival motif m ↑ that is always energetically favored than m 3 , proving m 3 in Fig. 3 undesignable by the following theorem. Another example of single rival motif is shown in Fig. 4b.

, then m ω is undesignable. The correctness of Theorem 3 follows Def. 5. According to RIGEND [35], the energy di!erence of two structures ##G → is totally decided by their di!erential positions, which can also be applied to two motifs. The condition in Theorem 3 can be written as

where

denotes the di!erential positions 1 , and

denotes the free energy di!erence between m and m ω . Therefore, we can verify a single rival motif by inspecting possible nucleotides on only these di!erential positions. Refer to the RIGEND [35] for details.

For a rival motif m ↑ satisfying Theorem 3, we have pairs(m ↑ ) ⇐ pairs(m ω ) (proven in Supplementary Section E). However, if any motif m ↑ satisfying pairs(m ↑ ) ⇐ pairs(m ω ) is not a qualified rival motif, more rival motifs will be required as evidence for undesignability.

The right side of Fig. 4 shows an example of target motif with multiple rival motifs. Identifying a set of multiple rival motifs is more complicated than finding a single rival motif. We present a high-level Algorithm 1 to elucidate the fundamental procedures involved in identifying rival motifs, providing readers with an overview of the essential steps. In Algorithm 1 there are three parameters M, N, and K. They limit the number of di!erential positions, rival structures and sampled sequences, preventing the algorithm running forever. The overall complexity is O(NM + NK|m| 3 ). We omit the intricate details for conciseness, and encourage readers to consult the literature of RIGEND [35] for a comprehensive description. Fig. 4: Example of target motif and rival motif(s). The target motif 4a is from the structure in Fig. 1, the target motif 4c is from Eterna100 puzzle "Mat -Elements & Sections" as plotted in Table Fig. 3.

if |M rival | > N then return unkown ω early stop 5:

if m →→ = uMFE(x, y \ m ω ) then return designable ω found successful uMFE design 8:

m →→ ↓ MFE(x) ω one of MFE structures in case of multiple 9:

if 4 |!(m → ,m ω )| < M then M rival ↓ M rival ↑ {m →→ } ω limit the size of di!erential positions 10: return undesignable 5 Rotational Invariance

In the nearest-neighbor model, the free energy change of a loop is independent of its absolute position or specific orientation within the structure. As a result, the free energy of motifs adheres to both translational invariance and rotational invariance, though not to symmetrical invariance. Fig. 5 shows two groups of equivalent motifs found in the Eterna100 puzzles, demonstrating rotational invariance. The motifs m a , m b , and m c come from puzzles with IDs #60, #81, and #88, respectively, while m d and m e are from the puzzle with ID #86 (refer to Table 3 for detailed structures with highlighted motifs). Among them, m a and m b can be rotated into each other, as can m d and m e . However, despite both containing three bulge loops, m b and m c cannot be rotated into one another.

To identify and represent such rotational equivalence, we propose a noval representation for motifs, referred to as loop-pair graph.

Definition 8. A loop-pair graph for a pseudoknot-free RNA secondary structure y is a weighted undirected graph G(y) = ⇔V (y), E(y)↖ where each node v → V is either a loop in y or a pair in y or the pseudo-pair node r (representing 5 ↑ and 3 ↑ ends rather than a base pair), (i.e., V (y) = loops(y) ⇑ pairs(y) ⇑ {r}) and each edge e = (u, v, w) → E(y) connects one loop node and one pair node, with the edge weight w denoting the number of unpaired bases of the segment of the loop between the connected pair and next pair according to the direction from 5 ↑ to 3 ↑ . For each loop node v, there is an ordered list N (v) of neighbor nodes.

The loop-pair graphs of the structure and motifs in Fig. 3 is shown in Fig. 6c. We also show Fig. 6a and Fig. 6b for comparison. The advantages of loop-pair graphs include: 5 ' e5 e' e3 e' (a) Polymer graph B E S M H S M S H S H (b) Loop graph ∝ B p E r p S p M p H p S p M p S p H p S p H 4 4 4 0 0 0 2 2 9 6 0 0 3 3 0 0 4 8 0 0 4 (c) Loop-pair graph ω rotate 5: return t 1. Bijective. A loop-pair graph contains all necessary information about loops, base pairs, and unpaired bases to fully reconstruct the original structure. In contrast, loop-graph in Fig. 6b or RNA-as-graph representations [16,11,10,36] cannot recover the original structure due to missing information about unpaired bases or helices, respectively. ignore helix stackings and can not recover the original structure. 2. Abstract. Loop-pair graphs emphasize the connections and topology of loops and base pairs within motifs, while abstracting away the finer details of the backbone structure. While other representations [5,19,18] also provide abstraction of structures, they serve for di!erent applications. 3. Compact. The number of unpaired bases is encoded as edge weights, which makes the representation more space-e"cient than the polymer graph in Fig. 6a.

RNA secondary structures are inherently recursive, making loop-pair graphs singly connected, essentially forming a tree. Any motif m ≃ y corresponds to an induced subgraph of G(y), containing the loop nodes for each loop in loops(m), the pair nodes for each pair in pairs(m), and all edges connecting these nodes. To assess the uniqueness of motifs under rotational isomorphism, we recursively rotate the graph representation of a motif using a boundary pair node as a pivot, as described in Algorithm 2 (linear complexity).

An ideal algorithm should be capable of identifying all minimal undesignable motifs within a given secondary structure. It is important to note that the sub-motifs of M always possess smaller cardinalities compared to M. Therefore, a straightforward approach involves enumerating all motifs in the structure according to their cardinality and determining whether each motif is designable or undesignable, as outlined in Algorithm 3. This algorithm assumes the existence of an oracle function, DECIDE(m), which returns whether m is designable or undesignable. While such an ideal function DECIDE(m) theoretically exists (exhaustive search Algorithm 3 Fully Bottom-Up Framework for Identifying Minimal Undesignable Motif

1: function BottomUpMotifDesignabilityScan(y) ω input a secondary structure y 2: M miniundesignable ↓ ⊋ ω a set to store identified minimal undesignable motifs 3: for all non-singleton m ↘ y in increasing order of card (m) do ω card (m) = 2, 3, . . . , |loops(y)| 4: if ≃m → ↗ M miniundesignable and m → ⇐ m then continue ω undesignable but not minimal 5: designablity ↓ Decide(m) ω either designable or undesignable 6: if designablity = undesignable then M miniundesignable ↓ M miniundesignable ↑ {m} 7: return M miniundesignable Algorithm 4 FastMotif (see Fig. 7 for an example of powerset) 1: global: M miniundesignable , M designable ω Global (minimal) undesignable and designable motifs 2: function FastMotif(y) ω Input is a structure 3: for all loop node u ↗ G(y) do 4: for all non-empty s ↗ 2 N (u) in increasing order of |s| do ω 2 N (u) : powerset of N (u);|s| = 1, 2, . . . , |N (u)| 5: m ↓ {u} ↑ s ω motif m has loop u and its neighbors in s, so card (m) ⇒ 2 6: if m ↗ M miniundesignable then continue ω check every rotated version of m; already identified 7: else 8: if ≃m → ↗ M miniundesignable and m → ⇐ m then continue ω undesignable but not minimal 9: designablity ↓ RivalMotifSearch(m) ω return designable or undesignable or unkown 10: if designablity = designable then M designable ↓ M designable ↑ {m} 11: else if designablity = undesignable then 12: if ⇑m sub ⇐ m, m sub ↗ M designable then M miniundesignable ↓ M miniundesignable ↑ {m} ω minimal

could achieve this), it may not be practical due to its high complexity. Nevertheless, it serves as a conceptual foundation for developing more practical algorithms.

Theorem 5. Given a secondary structure y, Algorithm 3 outputs a set M miniundesignable containing all and only the minimal undesignable motifs in y.

The proof is conducted by induction (detailed in Supplementary Section F.1). The total number of motifs in a structure can grow exponentially with cardinalities, making Algorithm 3 impractical for large structures. However, empirical observations suggest minimal undesignable motifs typically involve a small number of loops. To address this, we propose a variant of Algorithm 3, referred to as FastMotif (Algorithm 4), designed to identify as many minimal undesignable motifs as possible within a given structure y, while maintaining computational e"ciency. In particular, we limit our evaluation to motifs composed of a loop and any (nonempty) subset of its neighboring loops (Fig. 7). This approach o!ers several key advantages:

1. Each motif has a limited number of loops, making undesignability easier to decide. 2. For a loop v with k neighbor loops, i.e., |N (v)| = k, the size of N (v)'s power set 2 N (v) , excluding ⊋, is 2 k ⇓ 1. Since most loops have 2 or 3 neighbors, the number of motifs considered remains relatively small, while still covering most of the relevant small motifs. 3. Each loop and its neighbor loops can be seen as a small subgraph on the loop-pair graph G(y). Enumerating motifs in the power set would be equivalent to running Algorithm 3 on a local subgraph.

To enhance performance, we exclude motifs with more than 3 neighbor loops. The complexity of FastMotif is determined by the product of the number of motifs scanned and the complexity of Algorithm 1, making it polynominal. Additionally, FastMotif can be adapted to scan larger motifs. In Sec.8. We incorporated an undesignable substructure in Eterna puzzles ("Chicken feet" and "Mutated chickenfeet".) from RIGEND [35] and proved it is a minimal undesignable motif.

7 Related Work \ ⊋, i.e., {l 1 }, {l 2 }, {l 3 }, {l 1 , l 2 }, {l 2 , l 3 }, {l 3 , l 1 }, {l 1 , l 2 , l 3 }, only {l 2 , l 3 } and {l 1 , l 2 , l 3 }, when combined with l, are undesignable, but only {l, l 2 , l 3 } is minimal undesignable (see Tab. 3 for Eterna #57).

To the best of our knowledge, CountingDesign [31,30] is the existing method that has investigated undesignable motifs. However, it exhaustively enumerates and folds all RNA sequences for each motif group, identifying designable motifs and taking their complement to find undesignable ones. As a result, it is only

Fig. 8: A minimal undesignable motif with two rotational variants (top) found in 5S rRNA and SRP families.

applicable to short motifs, reporting motifs of up to 14 nucleotides. Another drawback is the limited interpretability of the undesignable motifs, as CountingDesign identifies them by taking the complement of designable motifs rather than directly characterizing the undesignable motifs themselves. Moreover, Count-ingDesign defines motifs as rooted trees starting from a base pair, making it unable to handle external loops in RNA structures. Additionally, it overlooks rotational invariance of motifs, leading to redundancy in the identified undesignable motif set. See also Sec. 8.3 and Supplementary Sec. C for e"ciency comparisons.

8 Empirical Results

We applied our algorithm FastMotif to two public RNA structure benchmarks: Eterna100 [2] and ArchiveII [8]. Eterna100 consists of 100 structuresfoot_0 , artificially designed by human experts, and serves as a primary benchmark for RNA design. ArchiveII, comprising native RNA structures, spans 10 families [13,25,9,7,24,38] of naturally occurring RNA and is used to evaluate RNA folding [15]. 3 Following prior work in RNA design [12,22,4,34] and undesignability [35,30,31,1], the RNA folding model is ViennaRNA (v2.5.1) [20]. Our code was written in C++, utilizing a 3.40 GHz Intel Xeon E3-1231 CPU and 32 GB memory. Parallelization was achieved by OpenMP for 8 CPU cores. The parameters during rival motif search (Alg. 1) are set as M = 10 10 , N = 10 5 , K = 100. Our source code is available at https://github.com/shanry/RNA-Undesign. 8.2 Undesignable Structures and Unique Minimal Undesignable Motifs 5' 3'

Fig. 9: Undesignable tRNA structure/motif. Table 2 summarizes the statistics of undesignable structures and (minimal) undesignable motifs, as well as the running time, for both Eterna puzzles and native structures from ArchiveII. Among Eterna100 puzzles, we found 24 unique minimal undesignable motifs (35 occurrences), resulting in 18 undesignable puzzles (Table . 3). This result is stronger than that of RIGEND, which identified 16 undesignable puzzles along with one rival (sub-)structure for each puzzle.

The structures in ArchiveII, on the other hand, are high-quality native structures, which intuitively should be designable. Surprisingly, there are over 1,000 occurrences of undesignable motifs from almost all ArchiveII families (except for Group II Intron). In total, we found 331 unique minimal undesignable motifs in ArchiveII, some of them shared across families, and 663 (17%) undesignable structures. For example, Fig. 8 shows a minimal undesignable motifs shared across two families and Fig. 9 shows the only undesignable tRNA structure and motif. See Supplementary Section H for more motif examples in 16S & 23S rRNA structures. We suspect the large number of undesignable structures and motifs are due to the energy model (Vienna 2) being imperfect and pseudoknots playing a role in designability which is beyond our work.

Interestingly, no motifs are shared between Eterna100 and ArchiveII, and in total we found 355 unique minimal undesignable motifs, which can be browsed on our web server http://linearfold.org/motifs. Users can even upload a new structure and the server will find minimal undesignable motifs in it on the fly. 7) 3 5' 3' 5' 3' 60: Mat -Elements & Sections 1 5' 3' 61: Chicken feet 2 5' 3' 67: Simple Single Bond 1 5' 3' 72: Loop next to a Multiloop 1 5' 3' 78: Mat -Lot 2-2 B 1 5' 3' 80: Spiral of 5's 1 5' 3' 81: Campfire 1 5' 3' 86: Methaqualone C16H14N2O 3 5' 3' 87: Cat's Toy 2 2 5' 3'

88: Zigzag Semicircle 1

91: Thunderbolt

3 5' 3' 92: Mutated chicken feet 3 5' 3' 5' 3' 96: Cesspool

8 5' 3' 5' 3' 99: Shooting Star 1 5' 3'

From Table 2, we can see the algorithm costs only a few seconds or minutes to scan an entire structure. Such e"ciency is much superior to the previous work CountingDesign. As a comparison, identifying undesignable motifs of length 39, the average length of minimal undesignable motifs identified in our work, would take thousands of years per motif using CountingDesign (Fig. SI 2). We also apply our rival motif search algorithm (Algorithm 1) to all motifs up to length 14 to compare with CountingDesign. We successfully identified all the minimal undesignable motifs (total: 4561; unique: 1805) in 0.7 hours, whereas CountingDesign takes more than a week. See Supplementary Section C for detailed comparison with CountingDesign.

We introduced a theoretical framework for loop-based motifs, and fast algorithms with a loop-pair graph representation to identify unique minimal undesignable motifs in RNA structures. By searching for rival motifs, the undesignability of motifs can be e"ciently confirmed and explicitly explained. Future exploration could involve implementing DFS/BFS-based algorithms to search for a broader range of undesignable motifs.

The results with ArchiveII suggest the current thermodynamic parameters are deficient. We hypothesize that improvements in parameterization [37,28] could be made, particularly from the perspectives of undesignability. Future work could involve comparing the sets of minimal undesignable motifs using alternative parameter sets beyond those implemented in the ViennaRNA package, including comprehensive parameterizations that account for coaxial stacking or that are informed by experimentally known structures [29,3,23].

A Loops in RNA Structures Table SI 1: Critical positions of loops in Fig. 2 Loop Type Critical Positions Closing Pairs Mismatches (Unpaired) External (3, 50) 2, 51 Stack (3, 50), (4, 49) Stack (4, 49), (5, 48) Multi (5, 48), (9, 24), (28, 44) 4, 49, 8, 25, 27, 45 Stack (9, 24), (10, 23) Bulge (10, 23), (11, 19) Stack (11, 19), (12, 18) Hairpin (12, 18) 13, 17 Stack (28, 44), (29, 43) Internal (29, 43), (32, 39) 30, 42, 31, 40 Stack (32, 39), (33, 38) Hairpin (33, 38) 34, 37

Table SI 2: Critical positions for each type of loops under Turner model implemented in ViennaRNA Special hairpins [21] of triloops, tetraloops and hexaloops are not considered here Loop Type Critical Positions Closing Pairs Mismatches External (i1, j1), (i2, j2), . . . , (i k , j k x ↓ map() 3: for i in I do 4:

x[i] ↓ xi ω Project the i-th nucleotide to index i 5: return x ii T. Zhou et al. 4 6 8 10 12 14 Motif Length 0 20 40 60 80 100 120 140 160 Running Time (hours) CountingDesign FastMotif (This Work) Cumulative Runtime CountingDesign 1.17 weeks FastMotif 0.7 hours Fig. SI 2: Running time comparison between FastMotif (this work) and CountingDesign for evaluating motifs of lengths up to 14. Algorithm 6 Contraint Intersection C ↑ = Intersection(C 1 , C 2 ) 1: function Intersection(C1, C2) ω C1, C2 are sets of constraints 2: (I1, X1) ↓ C1 ω I contains critical positions and X is a set of nucleotides compositions 3: (I2, X2) ↓ C2 4: I → ↓ I1 ⇔ I2 5: if I → = ⊋ then ω No overlapping positions; return original constraints 6: return C1, C2 7: X→ 1 ↓ {x ↖ I → | x ↗ X1} 8: X→ 2 ↓ {x ↖ I → | x ↗ X2} 9: for x ↗ X1 do ω Remove nucleotides compositions from X1 that is not in X2 10: if x ↖ I → / ↗ X→ 2 then X1 ↓ X1 \ {x} 11: for x ↗ X2 do ω Remove nucleotides compositions from X2 that is not in X1 12: if x ↖ I → / ↗ X→ 1 then X2 ↓ X2 \ {x} 13: C → 1 ↓ (I1, X1) 14: C → 2 ↓ (I2, X2) 15: return C → 1 ↑ C → 2 ω Return updated constraints

We compared FastMotif with the original CountingDesign [31] programfoot_3 to identify all undesignable motifs up to 14 nucleotides in length under the same setting (3.40 GHz Intel Xeon E3-1231 CPU and 32 GB of memory, with parallelization of 8 CPU cores). Fig. SI 2 shows the total running times of the two methods for identifying undesignable motifs of di!erent lengths. Both methods found all all the undesignable motifs (total: 4561; unique: 1805) and the designable motifs up to length of 14. However, the time cost of CountingDesign increases exponentially with motif lengths, highlighting its impracticality for longer motifs.

In contrast, FastMotif only need 0.7 hours. More importantly, FastMotif identified a set of rival motifs for each undesignable motif, which is explainable and helpful for further understanding RNA folding. Therefore, FastMotif demonstrates significant advantages in terms of not only scalability but also interpretability. 5' 3' Fig. SI 32: F.ananassa, 16S rRNA 5' 3' Fig. SI 33: F.ananassa, 16S rRNA 5' 3' Fig. SI 34: G.intestinalis, 16S rRNA 5' 3' Fig. SI 35: H.sapiens, 16S rRNA 5' 3' Fig. SI 36: H.sapiens, 16S rRNA 5' 3' Fig. SI 37: H.sapiens.mito, 16S rRNA 5' 3' Fig. SI 38: H.volcanii, 16S rRNA xii T. Zhou et al. 5' 3' Fig. SI 40: P.occultum, 16S rRNA 5' 3' Fig. SI 41: P.staleyi, 16S rRNA 5' 3' Fig. SI 42: S.cerevisiae, 16S rRNA 5' 3' Fig. SI 43: T.gondii, 16S rRNA 5' 3' Fig. SI 44: A.pyrophilus, 16S rRNA 5' 3' Fig. SI 45: T.maritima, 16S rRNA 5' 3' Fig. SI 46: Z.mays, 16S rRNA Supplementary Information xiii 5' 3' Fig. SI 47: B.burgdorferi, 16S rRNA 5' 3' Fig. SI 48: B.subtilis, 16S rRNA 5' 3' Fig. SI 49: C.elegans, 16S rRNA 5' 3' Fig. SI 50: C.psittaci, 16S rRNA 5' 3' Fig. SI 51: C.reinhardtii.chloro, 16S rRNA 5' 3' Fig. SI 52: C.reinhardtii.mito, 16S rRNA 5' 3' Fig. SI 53: D.melanogaster, 16S rRNA 5' 3' Fig. SI 54: E.coli, 16S rRNA xiv T. Zhou et al. H.3 23S rRNA Motifs and Structures 5' 3' Fig. SI 55: B.subtilis, 23S rRNA 5' 3' Fig. SI 56: B.subtilis, 23S rRNA 5' 3' Fig. SI 57: B.subtilis, 23S rRNA 5' 3' Fig. SI 58: E.coli, 23S rRNA Supplementary Information xv 5' 3' Fig. SI 59: E.coli, 23S rRNA 5' 3' Fig. SI 60: E.coli, 23S rRNA 5' 3' Fig. SI 61: H.pylori, 23S rRNA 5' 3' Fig. SI 62: H.pylori, 23S rRNA xvi T. Zhou et al. 5' 3' Fig. SI 63: S.aureus, 23S rRNA 5' 3' Fig. SI 64: S.aureus, 23S rRNA 5' 3' Fig. SI 65: S.aureus, 23S rRNA 5' 3' Fig. SI 66: T.thermophilus, 23S rRNA