RNA molecules fold into intricate shapes, and one of the central challenges of computational biology has been to run that process in reverse: given a desired shape, find a sequence of letters that will fold into it and nothing else. This problem, known as RNA inverse folding, has resisted a clean complexity classification for nearly three decades. Now a team of researchers reports that for a broad and practically important family of target structures, the problem can be solved in linear time, a striking contrast with the general case, which was shown to be computationally intractable only in 2020.
The new work, published in Algorithms for Molecular Biology by Théo Boury, Samuel Gardelle, Laurent Bulteau and Yann Ponty, establishes that inverse folding can be solved in linear time for every target secondary structure that contains no isolated base pair and no isolated stack. In the language of RNA structure, this means every helix, a run of consecutive paired positions, consists of at least three base pairs. The result is notable because it applies to structures that are typical of stable, biologically realistic RNA targets, which tend to avoid short, unstable helices.
To appreciate why this matters, it helps to understand what inverse folding asks. A secondary structure is a set of base pairs among positions in a sequence, with each position involved in at most one pair and no pairs crossing. Inverse folding seeks a sequence whose unique optimal fold, under a chosen prediction model, is exactly the target structure. In the base pair maximization model considered here, the optimal fold is the one with the most base pairs. A sequence that achieves this is called a design for the target.
The general problem is hard. Bonnet and colleagues settled the classic complexity question in 2020, showing that even a mildly constrained version of inverse folding in simple base pair models is NP-hard. Earlier, Schnall-Levin and coauthors had shown NP-hardness for a generalized version that includes the energy model as part of the input, but their reductions relied on manipulating the energy model itself, leaving the fixed-model case open. The 2020 result justified the large body of heuristic and exponential-time methods that practitioners had developed, from local search and bio-inspired metaheuristics to global sampling, constraint programming and neural generative models.
In parallel, Hales and colleagues had taken a structural view of the problem, characterizing families of designable and undesignable structures. They showed that saturated structures, where every position is paired, are designable if and only if their multiloop degrees do not exceed four. They also introduced separability, a condition on a coloring of the structure tree that is sufficient, though not necessary, for a sequence to be a design. Under their framework, a separated coloring can be converted into a solution sequence in linear time, painting a puzzling picture in which the general problem is hard yet many practical instances appear easy.
The new paper pushes this structural program much further. The authors first show that separability has intrinsic limits: there exist designable structures that admit no separated coloring, and there exist non-separable structures whose minimum helix length is two. They also prove that finding a separated design for a given structure is NP-hard, even when isolated base pairs are forbidden in the input. This means that, unless P equals NP, no polynomial-time algorithm can exist for separability in general, and the hope for one survives only when helices are of length three or more.
To escape this hardness, the authors introduce modulo m-separability, a refined version of the Hales condition that prescribes different modular values for the levels of paired and unpaired nodes in the structure tree. Deciding m-separability remains NP-hard in general, but the authors give a fixed-parameter tractable algorithm: for any input structure of length n, an m-separated sequence can be produced in time proportional to n times m times two to the power m, whenever such a sequence exists. Since practitioners can focus on small values of m, the exponential factor stays manageable.
The centerpiece is a theorem showing that any structure whose helices all have at least three base pairs is either trivially non-designable, because it contains one of two known undesignable motifs, or always admits a modulo-2 separated solution. Because a modulo-2 separated coloring can be found and converted into a sequence in linear time, inverse folding becomes solvable in linear time and space for this entire class. The authors also prove a matching characterization: for such structures, being designable, being 2-separable, and avoiding the two forbidden motifs are all equivalent conditions. They further show the bound is tight, since non-separable designable instances exist with minimum helix length one, and non-separable instances without isolated base pairs exist with minimum helix length two.
Beyond the guarantee for long helices, the algorithm remains useful for shorter ones. In exhaustive tests on all structures of length twelve, every designable target turned out to be separable, with the vast majority admitting solutions at modulus two. On a synthetic dataset of ten thousand random targets of length one hundred featuring at least one isolated stack, every target was separable, roughly eighty percent were 2-separable, and fewer than one percent required a modulus beyond six, with a maximum of nine. The authors caution that non-separable instances do exist, so this favorable behavior does not generalize to arbitrary lengths, but the large size of their counterexamples suggests the proportion of separable structures may remain non-negligible for relevant RNA target sizes.
The authors also tested whether these guaranteed solutions translate to more realistic energy models. Using the Turner nearest-neighbor model, they compared separated sequences against merely compatible sequences and against InfoRNA, a seminal local-search method. On targets of length one hundred with minimum helix length three, about thirty-five percent of separated sequences were successful designs by an energy-distance metric, versus ten percent for compatible sequences and forty-three percent for a relaxed variant that loosens multiloop constraints. InfoRNA performed surprisingly poorly, with only about one percent of its returned sequences optimal for their targets. Finally, the team showed that multidimensional Boltzmann sampling over separated designs allows fine control of GC content, from roughly thirty-two percent up to about fifty-one percent on their test set, suggesting these sequences are diverse enough to serve as seeds for future RNA design pipelines targeting realistic energy models.
Subject of Research: Computational complexity and linear-time algorithms for RNA inverse folding and secondary structure design.
Article Title: RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs
Article References: Boury, T., Gardelle, S., Bulteau, L., & Ponty, Y. (2025). RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs. Algorithms for Molecular Biology, 20(1), Article 20. https://doi.org/10.1186/s13015-025-00278-6
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00278-6
Keywords: RNA inverse folding, secondary structure, computational complexity, linear-time algorithm, separability, NP-hardness, fixed-parameter tractability, RNA design, base pair maximization, Turner energy model, GC content, dynamic programming
News Source: Drew Townsend. (October 30, 2026). RNA Inverse Folding Solved in Linear Time for Structures Without Isolated Stacks or Base Pairs. Scienmag.
