The Eterna100 With Other Models: A Short Review

  • 2
  • Idea
  • Updated 6 months ago
  • (Edited)
The development of the Eterna100 was a triumph in citizen science and Eterna. For those interested, here is a link to the original paper from 2016.
https://www.sciencedirect.com/science/article/pii/S0022283615006567

However, as mentioned in a previous forum post by Cynwulf28:
https://getsatisfaction.com/eternagame/topics/eterna100-summit
one of the limitations present in the Eterna100 is that they are based on puzzles designed using the Turner 1999 nearest neighbor parameters with Vienna 1.x. Since that time, several RNA structure prediction software have been integrated into the site, including Vienna2.x, NuPACK, and most recently the LinearFold versions of Vienna2.x and ContraFold. Over this past year, I published as many of the Eterna100 as possible using these other parameters. Here is a list of every puzzle in the Eterna100, and the ability to solve the secondary structure in other parameter sets.

https://docs.google.com/spreadsheets/d/1HwjM582R0oZ5Gk0Eft5Ym0sQvUMHh7Um7dWS5yqBdIg/edit#gid=0

 
Given this adventure in persistence, I decided to post the work here. We'll start with a short description for each puzzle set, why some puzzles are unsolvable, as well as the (completely subjective) "most difficult puzzle" to solve for each model. I would like to note that it is plausible that some of the puzzles that are unsolvable may actually be a mistake. Some puzzles are very large and I generally didn't try to solve a puzzle if I saw a motif that was unsolvable with previous motifs. However, there were several puzzles where I probably spent hours trying to find a solution given the possibility it works. So maybe you'll be able to scratch one off the list somewhere.

ViennaRNA2

https://eternagame.org/web/playerpuzzles/?size=100&search=[VRNA_2]The%20Alternate%20Eterna100&sort=solved

So, it turns out that VRNA_2 has something like 20 puzzles that are unsolvable using the secondary structures of the original Eterna100. We can break these up into two categories:

  1. Single Base Pair Structures: So a very large number of the puzzles chosen for the Eterna100 incorporated single base pair motifs into their structures. This leads to several unsolvable puzzles, such as https://eternagame.org/web/puzzle/547104/ Campfire, where the extended zigzag motif is unsolvable in Vienna2.x. There are several puzzles where the addition of a single base pair makes the structure solvable in VRNA2, but may defeat the purpose of puzzle difficulty.
  2. Number of multiloop branches: As the number of branches off of an internal multiloop increases, the free energy of the loop decreases at a rate faster than an external loop with an equal number of branches. If an external multiloop has a large number of branched helices, the sequence will form a "neck" helix, which may be only a few base pairs in length, to benefit from an internal multiloop with a large number of branches.
These structural motifs result in most, if not all of the unsolvable puzzles in VRNA2. The third attribute is also the reason why the puzzle https://eternagame.org/web/puzzle/8950194/ Taraxacum officinale by ariel19_89 is the most difficult to solve.

https://eternagame.org/web/puzzle/8950194/ Taraxacum officinale by ariel19_89

So it turns out this puzzle took me several hours over the course of several days to solve. I considered it unsolvable at one point given the amount of misfolding. Given sheer luck, I found a solution, and it is currently only solved by the player Wawan151, whose solution is not the same as my own. So at the very least, there are two unique methods of solving all of the branches off of the external loop central to this puzzle (Author's note, Brourd has misplaced his solution somewhere).

NuPACK

https://eternagame.org/web/playerpuzzles/?size=100&search=[NuPACK]The%20Alternate%20Eterna100&sort=solved

So unlike VRNA2, Nupack has the pleasure of being a far easier model to solve some puzzles in, while also having nearly 30 structures from the Eterna100 being unsolvable. The reasons for this vary slightly, but are quite similar to VRNA2

  1. Unpaired Nucleotides in Multiloops: It turns out that the parameters in NuPACK have a term for increasing the free energy of multiloops for each unpaired base added to the loop. This is good for certain predictions, given it leads to structures that may favor internal loops over multiloops. However, this means there are several unsolvable puzzles due to excessively large internal multiloops. It also means that external loops typically have a much lower free energy compared to internal multiloops, given the same rules for increasing free energy don't apply. Several Eterna100 puzzles have short helices connecting internal multiloops and external loops, resulting in them being unsolvable in NuPACK
  2. Not many special free energy bonuses: Unlike the Turner parameters, which provide free energy bonuses for specific 1-1, 2-2, and 1-2 loop sequences, the NuPACK parameters remove several of these. 1-1 and 2-2 loops are a recurring motif in the Eterna100, and this results in several puzzles being unsolvable. Finally, structures with a 1-X format cannot be boosted at all, resulting in a handful of unsolvable puzzles.
  3. Single Base Pair Structures: Just like VRNA2, the single base pair structures result in several motifs being unsolvable in NuPACK. This is further compounded by many of these motifs being related to 1-1 and 2-2 loops, which cannot be boosted in the same way.

Given this, NuPACK does have some quirks that work to its advantage. In particular, G-U base pairs that act as closing base pairs for multiloops have a malus of several hundred thousand kcal/mol. While this may seem to be a negative attribute, if manipulated correctly, it allows certain puzzles with a single base pair motif connected to a multibranch loop to be solvable.

As for the most difficult puzzle, the closest there is to that is https://eternagame.org/web/puzzle/8940638/ Cat's Toy 2 by Merryskies. While this didn't take several hours to solve, it requires extreme manipulation of the free energy of the puzzle to solve the single base pair hairpin loop, as well as the short helices connecting everything.

LinearFold-VRNA2

So while I haven't gone through every puzzle with this model, the assumption is that some puzzles with a very small solution space for long sequence with degenerate MFE structures may be unsolvable. In particular, Taraxacum officinale may be one such puzzle, but as stated above, the author has misplaced their solution. Otherwise, the thermodynamic parameters are identical to VRNA2, and most puzzles should be solvable in the LinearFold version.

LinearFold-ContraFold

Unlike ViennaRNA2 and NuPACK, the author solved every LinearFold-C puzzle without the help of initially knowing (or being able to view) the parameter set. The best description of this is the use of brute force to determine heuristics for solving these puzzles. For example, did you know?
  1. In Contrafold, several structural motifs can be boosted. This includes bulges, triloops, multiloops, internal loops, and other hairpin loops.
  2. The combination of stacking energy and base pairing energies for G-U base pairs results in parameters where helices containing G-U base pairs are incredibly unstable.
  3. Lone base pairs can be incredibly unstable. So much so, that some motifs are just unsolvable.
  4. The number of base pairs that a helix must contain to close some loops is significantly higher than NuPACK and Vienna.
  5. U-U boosting is the favored sequence for special motifs like 1-1, 2-2, and 1-2 loops.
  6. The base pair orientation for some loops determines its stability (Lower free energy).
  7. Contrafold isn't the model you want to solve repetitive structures/sequences, instead resulting in causing these motifs to fold into a variety of other structures that you don't want. Enough that some puzzles were (for now) placed as unsolvable.
  8. Kudzu took nearly 2 hours to solve AFTER knowing a number of these heuristics.
  9. Most likely single nucleotide bulges can be boosted, although I didn't need to find out.
These are just some of the rules that were ingrained into my brain in order to solve a number of these puzzles. In total, I was only able to solve 45 of the Eterna100 puzzles with LinearFold-C. Once the actual model parameters are added to the game, this number may increase a bit, but it's still most likely going to be at least 45 unsolvable puzzles, perhaps bringing that number to 55 solvable. This is due to several factors:

  1. Short helices: The Eterna100 has an obsession with short helices. Enough so that it causes a large number of puzzles to be unsolvable. Helices as long as 2, 3 or 4 base pairs may not be stable in some motifs, and many lone pairs are definitely not stable at all.
  2. Repetitive substructures: Some large puzzles have repetitive substructures, and while this isn't an issue unto itself, if the sequence required to solve a specific structure only has one variation, then it will most likely misfold.

Speaking of the most difficult puzzle, https://eternagame.org/web/puzzle/458872/ Kudzu by Quasispecies contains several short helices, very few solutions to some of the puzzle motifs, and loops that requires specific boosting to work. It took nearly two hours to solve, although that could be due to solving it from first principles that were derived from iterative sequence/structure manipulation. Being unable to look at the energies of loops is definitely a pain. Some of the other LinearFold-C puzzles were difficult to solve as well, but generally weren't impossible once there was a basic understanding of how the sequences fold.

Where do we go from here?

Once the parameters for Contrafold are added to the game, those puzzles will be published. They should be far easier to solve... Other than that.

There was an Eterna100 summit about a year ago now that I wasn't able to attend. Whatever their final verdict was may be the direction they choose to go with for the puzzles, however I will say this.

As we move towards parameters for secondary structure prediction that are more and more accurate, the more irrelevant the Eterna100 may be with regards to actual RNA structure design. Granted, the puzzles provide an excellent benchmark for algorithms that solve secondary structures, given they are naturally difficult in nature, but there is an over-reliance on difficulty from motifs that require specific solutions for specific structures. Especially, if those solutions are specific to one model over another. This would mostly affect algorithms that use machine learning of player sequence design, and not based on first principles like NEMO and others.

When I originally started the Alternate Eterna100, one goal of mine was to modify the structures of the Eterna100 with a minimum number of edits, allowing for the puzzles to be solvable in a model. This quickly spiraled out of control, as the definition of "minimum" was called into question, as well as whether these puzzles may potentially lose the ability to be unsolvable by bots without these motifs. So I now have a proposal for this.

First, the minimum number of structural mutations to a puzzle to make it solvable in every available model, as well as minimizing the change in free energy from one structure to another. So why this proposal? Well, consider a puzzle where you delete a single nucleotide bulge in a helix, making the entire helix stable. Deleting the bulge decreases the overall difficulty of the puzzle, and is only a single structural mutation. However, it may be a more drastic change to free energy than the addition of a base pair. An additional constraint could be to minimize the change in length to the puzzle.

Anyway, that could be an interesting way to design a new Eterna100, but maybe it would be easier to just pick new puzzles. Hopefully somebody found these musings and my work to be useful. In conclusion, perhaps nothing comes of this but about ~200 puzzles.

Cheers
Photo of Brourd

Brourd

  • 438 Posts
  • 79 Reply Likes

Posted 6 months ago

  • 2
Photo of Omei Turnbull

Omei Turnbull, Player Developer

  • 968 Posts
  • 304 Reply Likes
A new paper, Learning to Design RNA, was posted on arxiv.org that describes a machine-learning algorithm that the authors claim "achieves new state-of-the-art performance on all benchmarks", which included the Eterna100. Looking at their results on the 100, my first impression was to chuckle, since they only solved 65 of the 100. But then I saw that they were using Vienna2 as their energy model, which would make 65 more respectable. Still,  thanks to you effort we know they failed to solve (at least) 15 that were possible.

Do you know whether Nando tried NEMO on the 100 using Vienna2?
Photo of Brourd

Brourd

  • 438 Posts
  • 79 Reply Likes
I believe that reviewers asked about that with the paper, and last I heard Nando did use NEMO with the Vienna2 parameters.

It does kind of put the work of Runge et al. in perspective when they state they were able to solve 65% of the structures, when really they solved about ~80% of the puzzles. Difficult to make comparisons between algorithms without parity in the parameters.
(Edited)
Photo of Brourd

Brourd

  • 438 Posts
  • 79 Reply Likes
Also it would be cool to have a series of badges for solving the Eterna100 in other models :P
Photo of jandersonlee

jandersonlee

  • 549 Posts
  • 122 Reply Likes
In choosing the puzzles for the Eterna 100 list I did not take into account alternative energy models, merely how many human solvers they had, how (qualitatively) complex they looked, and if they seemed to have "unusual" features. In hindsight this might have been short-sighted, given that we already knew there were "unsolvable" puzzles in the mix that had been design with a prior energy model.
Photo of Brourd

Brourd

  • 438 Posts
  • 79 Reply Likes
I'd argue that the choices for Eterna100 were well made and are a fair sample of the incredible diversity of the database of Eterna puzzles. It would be difficult to find 100 puzzles that fulfill the requirements of multiple parameter sets, while maintaining the level of difficulty that scales across the 100 puzzles.

That being said, I think it could be possible to redesign each puzzle so that they are solvable in many different parameter sets. It would decrease the difficulty of some puzzles with one model versus another, but the redesign would predominantly affect puzzles with isolated pockets of difficulty, and definitely not affect macro folding or difficulty.

Given this, I'm considering undertaking this task once LinearFold-Contrafold is implemented back in the game. Perhaps somebody will have the time to benchmark these mutated Eterna100 puzzles against various solving algorithms using multiple parameters.
Photo of jandersonlee

jandersonlee

  • 549 Posts
  • 122 Reply Likes
That sounds like a worthwhile project for someone with your understanding of the various folding engines.
Photo of Brourd

Brourd

  • 438 Posts
  • 79 Reply Likes
My PhD adviser would probably beg to differ, but it gives me something to do in what little spare time I have.