Probabilistic RNA designability via interpretable ensemble approximation and dynamic decomposition

RNA design, also known as RNA inverse folding, aims to find RNA sequences that fold into a target secondary structure. However, recent work has shown that some target structures are provably undesignable, where no RNA sequence can fold into it as the minimum free energy (MFE) structure. In this paper, we go beyond this binary, MFE-based designability and explore a soft, probability-based designability that upperbounds the Boltzmann probability of any design and quantifies how easily or likely any design might possibly fold into the target structure. We introduce a theory of ensemble approximation and a probability decomposition framework for bounding the folding probabilities of RNA structures and motifs in an explainable way. We further develop a linear-time dynamic programming algorithm that efficiently searches over exponentially many decompositions. Combining ensemble approximation with dynamic decomposition search, our method efficiently identifies the optimal motif decomposition that yields the tightest probabilistic bound for a given structure. Our framework is applicable to any factorizable energy model or scoring function that decomposes onto loops.

Applying our work, LinearDecompose, to both native and artificial RNA structures in the ArchiveII and Eterna100 datasets, we obtained much tighter probability bounds than baselines. Our work also provides anatomical tools for analyzing RNA structures and pinpointing the sources of design difficulty at the motif level.

Source code and data are available at https://github.com/shanry/RNA-Undesign.