Old Dog, New Tricks: Exact Seeding Strategy Improves RNA Design Performances

The Inverse Folding problem involves identifying RNA sequences that adopt a target structure with respect to free-energy minimization, i.e., preferential to all alternative structures. The problem has historically been regarded as challenging, largely due to its proven NP-completeness of an extended version where the base pair maximization energy model is used. In contrast, it has recently been shown that a large subset called m-separable structures, notably including those comprising helices of length 3+, can be solved in linear time within the same energy model. This permits not only the identification of a single solution but also the characterization of a language of solutions. In this work, we seek to describe the “hardness” of Inverse Folding, bridging (at least heuristically) the gap between a simplified energy model and a more realistic Turner energy model. We used LinearBPDesign to generate seed sequences for RNAinverse, thereby improving the design process in a Turner energy model. To this end, we extended LinearBPDesign to accommodate biseparability and to handle non- or high modulo separable structures by minimalist addition of base pairs. Our study suggests that seeds generated by LinearBPDesign capture long-range interactions, thereby improving the performance of RNAinverse compared to seed focusing on refining the energy model itself. Most surprisingly, a significant number of LinearBPDesign seeds uniquely fold into the target structure in the Turner model, especially when helices are at least of length 2. This observation suggests that the “hardness” of design may arise from the intrinsic properties of the structures themselves.