For years, the Eterna100 benchmark stood as a formidable challenge in computational biology, a set of 100 complex RNA design puzzles. Now, a new algorithm named Montparnasse, developed by Tristan Cazenave, has achieved what many thought highly improbable: it has solved the entire benchmark, heralding a new era for synthetic biology, medicine, and nanotechnology.
The intricate art of RNA design
Ribonucleic acid, or RNA, is far more than just a messenger for DNA. These versatile molecules are critical players in countless biological processes, from regulating gene expression to catalyzing biochemical reactions. Their function is intricately tied to their three-dimensional shape, which is largely determined by how a linear sequence of four nucleotide bases—Adenine (A), Cytosine (C), Guanine (G), and Uracil (U)—folds back upon itself to form a stable “secondary structure.”
The “RNA design problem,” also known as the Inverse RNA Folding problem, asks a tantalizing question: can we devise a sequence of these A, C, G, U bases that will reliably fold into a *pre-determined* target shape? The ability to do so would be a game-changer. Imagine crafting custom RNA molecules as tiny biological machines for targeted drug delivery, as components of sophisticated biosensors, or as building blocks for intricate nanostructures.
“The design of molecules with specific properties is an important topic for research related to health,” Cazenave states in his paper, highlighting the profound implications of this challenge.
However, this design task is incredibly complex. With four possible bases at each position in an RNA strand of length $N$, the sheer number of potential sequences ($4^N$) grows exponentially, creating a vast search space that quickly becomes unmanageable for even moderately long molecules. Finding the one-in-a-billion sequence that folds *just right* is a monumental computational hurdle.
The Eterna100 benchmark, featuring 100 unique RNA secondary structures (often represented in a “dot-bracket” notation), has served as the proving ground for RNA design algorithms. Over the years, numerous sophisticated methods have been thrown at these problems, including adaptive random walks, stochastic local searches, and genetic algorithms. Programs like INFO-RNA, MODENA, and NEMO made significant headway, with NEMO, for instance, solving 95 of the 100 problems.
More recently, GREED-RNA emerged as a state-of-the-art program, employing greedy initialization and mutation strategies alongside multi-objective evaluations to sort and refine potential RNA sequences. Even powerful approaches based on Monte Carlo Tree Search (MCTS) and Generalized Nested Rollout Policy Adaptation (GNRPA) had, until now, fallen just short of conquering the entire benchmark, typically solving around 95 problems.
Tristan Cazenave’s Montparnasse framework introduces a suite of algorithms, culminating in the star performer: **MOGNRPALR** (Multi Objective Generalized Nested Rollout Policy Adaptation with Limited Repetition). This algorithm isn’t just an incremental improvement; it represents a significant leap in search strategy.
Montparnasse first refines existing ideas. It includes MOGRLS (Multi Objective Greedy Randomized Local Search), a simplified yet more effective version of GREED-RNA’s local search, and PN (Progressive Narrowing), which intelligently manages multiple search paths before focusing on the most promising ones. But the real breakthrough lies with MOGNRPALR.
MOGNRPALR cleverly combines the strengths of GNRPA (which generalizes Nested Rollout Policy Adaptation with a prior bias) and GNRPALR (which prevents search stagnation by limiting repetitions) with the multi-objective evaluation criteria previously seen in GREED-RNA. Think of it as an AI that learns to play the RNA design game with extraordinary skill:
- Nested search levels: The algorithm explores solutions at different levels of abstraction. At each level, it makes numerous calls to a lower level, refining its strategy (or “policy”) based on the outcomes. This hierarchical approach allows for a more focused and efficient exploration of the vast sequence space.
- Adaptive policy: For each search level, MOGNRPALR maintains a “policy”, an array of weights associated with potential moves (i.e., choosing a specific nucleotide at a specific position). It iteratively refines this policy, reinforcing choices that lead to better RNA sequences (those closer to the target structure based on multiple criteria like base pair distance, ensemble defect, etc.).
- Intelligent playouts: At the lowest level, a “playout” function constructs an RNA sequence step-by-step. This isn’t random; it’s guided by the learned policy weights and biases (e.g., favoring G-C pairs for stability), using a Boltzmann sampling (softmax function) to probabilistically select the best next move. The probability $p_m$ of choosing a move $m$ is given by $p_m = frac{e^{w_m+beta_m}}{sum_k e^{w_k+beta_k}}$, where $w_m$ is the policy weight and $beta_m$ is a bias.
- Limited repetitions: A crucial innovation from GNRPALR is to stop iterations at a given level if the same best sequence is found a second time. This prevents the algorithm from becoming too deterministic and getting stuck in local optima, encouraging broader exploration.
The `adapt` function is key: it modifies policy weights to reinforce the best sequence found at the current level, increasing the weights of moves in that sequence and decreasing others proportionally to their play probabilities. This online learning allows MOGNRPALR to quickly zero in on promising regions of the search space.
Raphael’s masterpiece may not be all his
The true power of MOGNRPALR became evident when pitted against the Eterna100 v1 problems. Cazenave reports that by running 200 MOGNRPALR processes in parallel, **all 100 problems were solved in less than one day.** This is a landmark achievement.
The paper highlights performance on some of Eterna’s most notorious puzzles:
- Problem 99 (“Shooting Star”): MOGNRPALR solved this puzzle in 120 out of 200 runs (60% success rate). In stark contrast, GREED-RNA, a strong prior contender, only managed 6 successful solutions (3%). The MOGRLS and PN algorithms from the Montparnasse suite showed intermediate success rates of 9.5% and 14% respectively.
- Problem 90 (“Gladius”): A notoriously difficult structure. After a day of computation, MOGNRPALR found multiple solutions, while GREED-RNA failed to find any, with its best attempt still being 2 base pairs away from the target.
- Problem 100 (“Teslagon”): Another tough case where MOGNRPALR significantly outperformed GREED-RNA, discovering many more solutions.
These results demonstrate not just incremental gains, but a qualitative shift in capability. MOGNRPALR’s ability to navigate the complex energy landscapes of RNA folding and consistently find optimal or near-optimal sequences for diverse target structures is remarkable.
The Montparnasse framework, and particularly its MOGNRPALR algorithm, represents a triumph of sophisticated search techniques applied to a fundamental biological problem.
