An algorithmic solution to Eterna100's Shooting Star

Shooting Star is puzzle 99 of the Eterna100-V2 RNA design benchmark: a 370-nucleotide target fold full of junctions and isolated base pairs. Eterna players have solved it under the ViennaRNA 2 folding engine, but no algorithm has in the benchmark's published runs; an automated solution would close one of the last three gaps between design programs and human players on this benchmark.

Problem

Let $y^\star$ be the Eterna100-V2 target below in dot-bracket notation (370 nt; Eterna puzzle 9597797):

(((((((((((((((((...(.(..((.(((.(((.((....).))).)))).).)..))..))))))).(((((..(.(..((.(((.(((((.(((.((((.((....).)))).))))).))).)))).).)..))..)((....))..))))(((((((((...))))).(((((...)))))(.(....).).)))).)))).((((.((((...(((((((...))))))).(((((...)))))))))(((((((...))))))).(((((...)))))))))((((..((....))(..((..(..(.(.(((.((((.((....).)))).)))).)..)..).))..))))).)))))).

Using a method that receives only $y^\star$, find a sequence $x \in \{\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{U}\}^{370}$ with

$$\arg\min_{y} \Delta G(x, y) = y^\star,$$

where $y$ ranges over pseudoknot-free structures with A–U, G–C and G–U pairs and $\Delta G$ is the Turner 2004 nearest-neighbour free energy at 37 °C computed by ViennaRNA 2.6.4 with default settings (dangles = 2). In practice, stock RNAfold -T 37 must print exactly $y^\star$; on a tie, the printed structure counts. Player solutions and hand edits for this puzzle are not allowed.

The target has 126 base pairs, 26 of them isolated (stacked on neither side), 20 one-nucleotide bulges, 12 internal loops and seven multi-branch junctions: four four-way and three three-way.

Background

Eterna player Brourd posted Shooting Star in 2012, and it entered Eterna100 in 2016 (Anderson-Lee et al.). Its original target could not be solved under ViennaRNA 2 parameters; for V2, players made it solvable by adding just three base pairs to a structure with 29 isolated pairs (Koodli et al., 2025). Zhou et al. later proved the original target undesignable under a unique-MFE criterion (2025), so the V2 target is the one a design method can aim for.

What is known

• Eterna players have solved the V2 target with Vienna 2; a sample player solution is in the benchmark data (Koodli et al., 2025).
• In the benchmark authors' runs (ViennaRNA 2.6.4, one core, 24 hours), none of RNAinverse, EternaBrain, LEARNA, SentRNA, NEMO or DesiRNA solved it.
• DesiRNA's authors report 97 of the 100 V2 targets solved, and their published solutions omit this one (Wirecki et al., 2025).
• With ViennaRNA 2.5.1 parameters, no sequence has the original V1 target as its unique MFE structure (Zhou et al., 2025), in line with the players' finding that it could not be solved under Vienna 2.

What would count as progress

• A 370-nt sequence for which stock RNAfold -T 37 (ViennaRNA 2.6.4) prints exactly the target, made by a program from the target alone. The check takes under a second.
• The program, settings, random seed and run time, so the run can be repeated. A run within 24 hours on one core would add this puzzle to the Eterna100-V2 count.
• A design in which the target is the unique MFE structure, with no tie (checkable with RNAsubopt -e 0), is a stronger result.

References

1. R. V. Koodli et al. Redesigning the Eterna100 for the Vienna 2 folding engine. bioRxiv (2021, revised 2025). doi:10.1101/2021.08.26.457839
2. J. Anderson-Lee et al. Principles for predicting RNA secondary structure design difficulty. J. Mol. Biol. 428, 748–757 (2016). doi:10.1016/j.jmb.2015.11.013
3. T. K. Wirecki et al. DesiRNA: structure-based design of RNA sequences with a replica exchange Monte Carlo approach. Nucleic Acids Res. 53, gkae1306 (2025). doi:10.1093/nar/gkae1306
4. T. Zhou et al. Scalable and interpretable identification of minimal undesignable RNA structure motifs with rotational invariance. RECOMB 2025, pp. 153–174. doi:10.1007/978-3-031-90252-9_10

Source

Imported from Eterna100 V2 puzzle 99, curated by Eterna / Das Lab, Stanford. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.