Repetitive RNA strands built from the same three-letter block over and over have become a favorite tool of synthetic biologists, because they can spontaneously assemble into droplets that act as clean rooms inside cells. But predicting how these triplet repeat RNAs fold, and how they interact with one another, has long been a computational nightmare. A new study published in Algorithms for Molecular Biology by Kimon Boehmer, Sarah J. Berkemer, Sebastian Will and Yann Ponty now delivers a suite of faster algorithms that turn some of these intractable problems into ones that can be solved in linear or polynomial time, while carefully mapping out where the difficulty remains irreducible.
The researchers focused on the minimum free energy (MFE) secondary structure, the shape an RNA adopts when it minimizes its thermodynamic cost, and on the partition function, which sums the statistical weight of every possible structure in the Boltzmann ensemble. For ordinary RNA sequences, folding by energy minimization is a classic dynamic programming problem historically solved in cubic time, and the best known algorithm to date runs in about O(n^2.8603). Prior work has even shown that a substantially faster general algorithm would refute the Strong Exponential Time Hypothesis, one of the cornerstones of complexity theory. Triplet repeats, however, carry a hidden regularity that the new study exploits to sidestep these barriers.
The key insight is deceptively simple: because the sequence repeats every three bases, any region of the molecule can be shifted three positions left or right and remains identical. This means a dynamic programming algorithm no longer needs to track every possible starting index, only three of them, collapsing a linear dimension of the problem to a constant. The authors also observed that the graph of allowed Watson-Crick and wobble base pairs contains no triangles, which forces every base pair in an optimal structure to involve one particular letter, which they call the covering letter. Together, these symmetries let them characterize the MFE structure of a triplet repeat RNA almost in closed form.
The resulting characterization is striking. Determining the MFE is thus reduced to a simple calculation taking logarithmic time in the explicit length of the sequence, and the structure itself can be reconstructed by a linear-time algorithm. The optimal structure is not always unique: for the GCU repeat, the number of distinct optimal structures can grow exponentially with the number of repeats, since each layer of the helix offers a choice between two possible pairings.
The same machinery extends to the Turner nearest-neighbor energy model, the standard thermodynamic model used in modern RNA folding software. Under mild assumptions on the multiloop parameters, which the authors verified are satisfied by the Turner 2004 parameter set, they prove that optimal structures contain no multiloops, so the canonical single-helix form persists. The partition function can likewise be computed in linear time: the researchers translated the folding grammar of a triplet repeat into a system of algebraic generating function equations, whose coefficients obey a linear recurrence with polynomial coefficients, allowing the partition function to be evaluated with a number of arithmetic operations proportional to the number of repeats.
Interactions between multiple RNA strands are a harder class of problem. For a fixed set of strands, energy minimization was already known to be APX-hard, and the best previous algorithm for the partition function over multiple strands, due to Dirks and colleagues, ran in factorial time because it had to consider every ordering of the strands. The new study replaces that factorial blow-up with an exponential one. Instead of enumerating circular permutations one by one, the algorithm builds up values for all possible strand orderings simultaneously while exploring joint secondary structures, achieving a running time of O(3^m times n cubed) for m strands of total length n.
The authors then show that even restricting to triplet repeats does not make the fixed-strand interaction problem easy. They prove that deciding whether a set of triplet repeat strands has a secondary structure with free energy below a threshold is NP-complete, under a reasonably intricate energy model with base pair rewards, multiloop penalties and strand association bonuses. The reduction is from a strongly NP-hard partitioning problem, and it works despite a curious feature of the setting: concatenating any number of CAG-type strands always yields the same sequence, so the only extra difficulty compared to single-strand folding is that the algorithm does not know where the strand borders lie. They also provide an XP algorithm parameterized by the number of distinct strand lengths, which they argue is, in a sense, the best one can hope for under standard complexity assumptions.
The most practically useful contribution is a polynomial-time algorithm for a different setting the authors call the strand soup. Rather than a fixed set of strands, the input is a base collection of sequences, and the algorithm must find the best connected structure over m strands drawn from that soup, where each sequence may appear zero or many times. This models synthetic biology scenarios in which strand concentrations are in excess and sequences are effectively infinitely available within the reaction volume. Using a connectivity bit in the dynamic program to enforce that all strands end up in a single complex, the soup interaction problem is solved in O(n cubed times m squared times p cubed) time for a soup of p distinct sequences, and a variant incorporating a simplified nearest-neighbor energy model runs in O(n to the fourth times m squared times p cubed).
To demonstrate the algorithms’ biological relevance, the team implemented the soup algorithm, which they call SoupFold, together with a partition function version and stochastic backtracking, and ran experiments on how triplet repeat strands interact. Heterogeneous soups proved far richer: different triplet patterns can achieve more base pairs than the theoretical upper bound for a homogeneous pool, and the probability that a base pair forms between two strands of different patterns depends strongly on which patterns meet and on the number of interacting strands, only converging at high strand counts.
From these interaction probabilities the authors distilled a design principle for synthetic biology. Some triplet repeats aggregate into liquid-liquid phase separated droplets that can isolate engineered circuits from the cell’s native clutter, and a modified bacterium performing many independent tasks would benefit from a set of repeat patterns whose members rarely pair with one another, a notion of orthogonality. Running SoupFold on these four patterns confirmed that the probability of exterior heterogeneous base pairs stays clearly below 0.2 across strand counts from one to ten, offering experimentalists a concrete starting palette of mutually orthogonal repeat building blocks.
Subject of Research: Computational algorithms for predicting the folding and interactions of RNA triplet repeat sequences
Article Title: RNA triplet repeats: improved algorithms for structure prediction and interactions
Article References: Boehmer, K., Berkemer, S. J., Will, S., & Ponty, Y. (2025). RNA triplet repeats: improved algorithms for structure prediction and interactions. Algorithms for Molecular Biology, 21(1), Article 4. https://doi.org/10.1186/s13015-025-00292-8
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00292-8
Keywords: RNA triplet repeats, secondary structure prediction, minimum free energy, partition function, RNA-RNA interaction, dynamic programming, computational complexity, NP-hardness, synthetic biology, liquid-liquid phase separation, strand soup, orthogonality
News Source: Gregory Coleman. (November 5, 2026). Faster Algorithms Decode the Folding Rules of RNA Triplet Repeats. Scienmag.
