Thank you to Omei for suggesting that I create this Thread.
As mentioned in the Eterna News Post (http://www.eternagame.org/web/news/8578227/) there is going to be a small, but nonetheless important summit held at Stanford on February 19th. In lieu of this I wanted to get the discussion going so that we are all as prepared as possible for this event. Also, if you know that you will not be able to attend (either in person or digitally) live on the 19th, this Forum thread can serve as a platform for you to voice your questions thoughts and concerns here in advance.
For those of you who are new, see the link at the start of this post for event specifics.
Brief history (feel free to correct me if I speak in error here): Eterna was started as a way to complement/augment the modeling RNA secondary structures in silico (through simulations). RNAs are possibly the most important class of all biological molecules: RNAs carry the coded message for proteins (mRNAs), deliver the building blocks of proteins (tRNAs), and are an integral component of those proteins assemblers, the ribosomes (rRNA). All living things are composed of cells and most of the structural and functional components of cells are proteins. But RNAs do far more than just serve to make proteins. RNAs act as tags which can up regulate (increase) or downregulate (decrease) how much of a given protein is made. It turns out that protein levels must be maintained at very specific levels to ensure the health of an organism. When an organism IS sick, one way to determine the cause of the sickness is to look at the RNAs being made; a sudden increase or decrease in levels of a particular RNA often serves as a marker for a particular disease and thus can serve to diagnose and ultimately treat whatever is ailing the organism in question. And RNAs can actually BE the source of disease as many Viruses store their genes in RNA genomes which they inject into a host upon infection. And just like proteins, RNAs can fill many functional roles, such as cutting up other RNAs or serving as labels that recruit other RNAs or proteins in an organism. <br/><br/>
How RNAs function and are regulated in living organisms is a direct result of how these molecules fold up. Thus, knowing what shape an RNA molecule will fold into is extremely important for Medical Science and the Biological Sciences in general. Computer Algorithms (Folding Engines, aka, the “Bots”) have historically performed poorly when predicting what shape an RNA will fold into based on the RNAs sequence and these same algorithms have also fallen short when predicting which sequences will fold into a given shape. The purpose of Eterna is to further the field of RNA research and design (especially in Medicine) through the insights obtained from human players. It turns out that Humans are STILL better than their computer-based counterparts at solving the problems facing RNA science. The Eterna 100 challenge was a “benchmark”, a standard meant to be a fair and balanced test of an algorithm’s ability to solve RNA shape puzzles across a diverse range of design types. Those algorithms tested in the initial study were RNAinverse, INFO.RNA, RNA.SSD, NUPACK, DSS.Opt, and MODENA. The results of the algorithms were tested against each other and compared to designs (RNA sequences) submitted by human players. The consensus was that humans are better at RNA design. A paper was published looking at where the Bots had failed and suggested ways in which the algorithms could be improved for better prediction and design. <br/><br/>
Now several years have passed and the Bots are back! Researchers have had time to improve these algorithms, building on the lessons learned through years of research (both from Eterna and other sources). So, the questions of old come back: are humans still better than Bots? Where do Bots fail? Where do Bots excel? What can the writers of algorithms learn from human players? What can human players learn from the Bots? And if there is to be a NEW Eterna 100, what would this New benchmark consist of? I look forward to hearing your thoughts, Please leave comments below, they are always welcome :-D
Thank you very much for starting this thread!
I find your your description of RNA wonderful. It puts well in perspective why RNA is extremely important to both disease and health.
I will try address some of your questions.
Also I can't help but put in a bit of lab perspective, despite the Stanford summit is about an in silico bot solver and the eterna paper was also mainly focusing on the puzzle side of the RNA folding problem. This is because lab is the direct link to later practical use of RNA in relation to medicine.
Are humans still better than Bots?
Yes, for spotting structural and sequence patterns.
No, I'm pretty sure that the bots (Vinnie included) can solve puzzles that I'm not capable of solving or patient enough to solve.
Yes, because we are better at recognizing the discrepancy between what the Bots allow and what is allowed in lab. Those two are not well in synch.
Yes, because I yet to see a bot design (switch) puzzles and solve as well as Cynwulf. ;)
Where do Bots fail?
From what I have seen the bots don't seem to see the puzzles as wholes, but solve the elements as local and unrelated parts. They need a more global puzzle perspective. Be able to recognize structural elements, repetitiveness, stem lengths, asymmetry and symmetry etc. See the "personality" of the puzzle.
Example 1: Vienna attempted solving our lab puzzles with wildly uneven energy distribution - like one stem solved with mainly GC pairs and another solved with mainly AU pairs. That won't fly in static lab.
Example 2: Visual structure. Basic visual structures stand out to humans. Symmetry was one of the things that got the in silico bots in trouble for static RNA. Symmetry will also get static RNA labs in trouble while helping for switch labs.We learned to avoid symmetry for static lab puzzles.
Example 3: A puzzle needs a change in solving style just depending on if its stems are in general short or long. I haven't seen the bots vary their solve style depending on the puzzles they are in. The lab will demand a higher GC ratio for designs with short stems and a higher AU ratio for design with long stems.
Example 4: Zero use of GU's. I have seen some of the bots solve without the use of GU's. This is an error both in silico and in lab. GU's are needed for creating variation. In particular the larger the puzzle gets.
Where do Bots excel?
Example 1: Try out weird things. Bots are way better at trying out weird stuff in the loops that most humans may not consider.
Example 2: If they solve, they are fast at solving.
Example 3: InfoRNA excel at making switchable sequences
I had trouble solving puzzles in a way that would make them good for making switches. InfoRNA solved that for me.
What can human players learn from the Bots?
Just watching how the bots solve is great for learning. Both for what not to do, but also for what to do. Just seeing what a bot does or another human players, make you more aware of your own approach, and make you think about what may work better.
Example 1: For some of our early labs the bots were better than us at making a particular lab structure. (The neck) We borrowed that structure from the bots and fused with our otherwise working designs.
Example 2: Lane sharing in switches, where inputs compete for a landing site in an RNA sequence turned up in EternaBot solves. Players nicked that approach.
What can the writers of algorithms learn from human players?
Bot algorithms needs to be more connected to how lab behaves. Not just how the energy model behaves. A lot of the pretty shaped single state puzzles we have been capable of making are just artifacts of the energy models.
Also what we as players are good at are varying our approach, just depending on what type of puzzle we are working on. We don’t treat every puzzle the same. Similarly I suspect that not every class of RNA will need the exact same approach for a lab solve either.
Example: Static and switch RNA takes a whole different solving and sequence style. Having a bot try do both, will not make any of the puzzle types happy. I suspect that specific classes of RNA may need a specific approach. While the overall RNA designing rules are the same.
Bot algorithm maker, this is for you :)
This blog post is an perspective on the difference between Bots and what works in lab.
Return of the Bots!
I recall Rhiju saying that just having a in silico bot that could solve puzzles better, would be valuable on its own.
Even if it wasn't good for lab. (I off cause did ask. :) )
So this was what we have been toying with, making puzzles that in different ways would test the limits of the bots.
Towards better RNA folding algorithms
A good deal of the Eterna100 puzzles were picked from puzzle groups that we knew would get the bots in trouble.
Some natural RNA's and easy Eterna puzzles were thrown in as well.
My personal concern is if the bots get better at solving puzzles as players, they get worse at solving for lab.
A puzzle bot capable of solving a good deal of the Eterna100 puzzles will have copied both the best and worst feature about us human players. Especially if it can solve the hardest of the puzzles.
The best feature about us is that we are great cutting corners in the energy models and finding their weaknesses - where they do not behave as lab.
This is also the worst feature about us, as some of the corners never ought to have been cut. As a lot of the puzzles we are able to solve and the bots failed on, are abominations to nature.
Put short: If bots get better at solving puzzles as players, they will get even faster to the wrong place.
Take the symmetric snowflake designs as example: They caused the bots trouble, while we could solve them. But static RNA lab would hate them.
So if this new puzzle bot is better at eg solving symmetrical structures, it will be bad news for static RNA lab. However I would very much like to borrow this bot for helping me making switches. :)
If there is to be a NEW Eterna 100, what would this New benchmark consist of?
I would like to see the original Eterna100 puzzles run in lab. To see how many of those structures could actually be made stable. Certain groups of puzzles, like the bigger symmetric and repeat element puzzles I expect would fare poorly. Except if they are put up as switches. ;)
But since I expect this to take a while, I would like to see a switch version of Eterna100 containing different groups of switches puzzles.
That has structural features related with lab switches
That has sequence features related with lab switches
That are hard for humans
That we suspect will be hard for the bots
Plus I have a thing for snowflakes. For those who have not yet seen, check out the Snowflake Challenge.
Thank you, Eli, for this great follow-up.
I understand what you are saying about balancing Bot training. We would like them to succeed all around, but using traditional Bot learning methods will provide Synthetic Model Masters which are failures in Wet Lab. Before I continue I want to comment on what has been said by Eli Fisker and quantropy. A common problem of Bots is that they are single minded. I propose a solution to this which perhaps some of you can exploit in enhancing your Bot design: Give the Bots multiple personalities. As mentioned above, players can switch tasks and specialize to the task at hand (such as solving a player-made puzzle) while being able to switch back to another task (such as Lab puzzles) without having forgotten what they learned about either. Bots learn as they go along just as we do, but that information seems to be homogenized into a unified puzzle-solving theory. The truth of the matter is that we don’t yet have a one-size-fits-all model to use in regards to RNA, there are a number of models which exist (https://en.wikipedia.org/wiki/List_of_RNA_structure_prediction_software) and they all have their specialty. <br/>
So, I propose we give the Bots a transmission so that they can shift between gears (the personalities I spoke of earlier) while solving puzzles...just like on would with a car. Use a high ‘gear’ for fast synthetic design solves (especially where blunt-force-solving works) and a lower ‘gear’ for Lab puzzles which require a more nuanced approach. The different gears could be selected from: 1) a listing to fit the situation, based on criteria, OR 2) the gears could be rotated through so that different approaches are applied to each design, with the best design following each approach being saved in the memory while gears are shifting.
Clarification...what do I mean by gears? I am not saying that we switch energy models in the middle of solving a puzzle (though that possibly could benefit the quality of some Lab puzzle solutions). Rather, what I propose is to different refinements of a given model, <br/><br/>
solve with lowest energy possible (lots of strong GC bonds and standard boosts),
or solve with higher energy whenever possible, (lots of AUs),
perhaps a gear where the Cs is GC pairs are mutated to Us whenever possible,
or perhaps a gear set up to maintain a certain ratio of GCs to AUs to GUs in every puzzle solve so that the solution reflects the ratios found in nature,
...if done is series (my second selecting option) then these sorts of gear shifts begin to resemble a ‘lather, rinse, repeat’ recipe for puzzle solving.
Some setbacks. <br/>
I do not know if this is true (correct me if I am wrong) but I get a feeling that older Bots either solve from lowest position #1-towards the final position within a RNA sequence, or start out with some basic template which they then mutate at random until by chance a solution emerges. The newer Bots if I understand correctly solve based DIRECTLY from the actual moves that players make while solving puzzles in Eterna. For a good number of static Eterna puzzles solving in silico is simple: 1) select the GC paintbrush, 2) shake cursor back and forth over the design of the puzzle in question until all stems are filled with GC pairs, 3) Bubbles! You can literally solve with your eyes closed. As we know from Labs all GC or all AU designs are very unfavorable in nature...the possibility for mispairing is to high. If the Bots are learning from us, then for simple designs with long stems, the bots will have learned from our ‘bad behavior’. So how do we correct bad Bot behavior? I suggest that we impose some mild constraints on the Bots in the form of a ‘finishing move’ ...a sort of ‘glaze’ which will compensate for the poor design by mutating some GCs to AUs or AUs to GC to achieve a more natural balance of base pairs in the final design.I’ll post more later... but I want to hear your feedback first. Let me know what you are all thinking :-D
I probably should have opened with this, but at long last here’s the fun stuff.
We have talked about the Bot side of things, but haven’t discussed the puzzles yet, so let’s change that.
The Eterna 100 standard was and is a collection of 100 puzzles made by players which were meant to test the solving capabilities of the Bots. The puzzles themselves were selected for diversity of design (structure) and in particular were selected to showcase those secondary structures which pose a challenge to Bots and Human solvers alike including: short stems, adjacent multiloops, Loop next to multiloop, bulges, internal loops, zig-zags, overly simple designs, and fractal like patterns (https://www.sciencedirect.com/science/article/pii/S0022283615006567#f0010).
As these 100 puzzles were used last time, it makes sense to test the current Bots against them. But these puzzles were made in the comparatively early days of Eterna, so the question stands...should the puzzles used for the Eterna 100 be updated? First let’s consider single State puzzles... are there structures which weren’t tested before? If so, what structural motifs would you suggest? Are there puzzles which you think SHOULD be part of the Eterna100 registry which aren’t there now?
Perhaps puzzles should be chosen based off of difficulty...I had a chance to speak with Dr. Rhiju Das at Eternacon2017 and in the course of conversation suggested that we upgrade to the Eterna1000, the list of wawan151 puzzles. Though I spoke partially in jest, maybe testing the Bots against some of his unsolved puzzles might not be a bad idea. There are a number of players with puzzles which no one has yet solved and wawan151 leads the pack with 249 ‘0 solver’ puzzles. Those other players with 0-solver single state puzzles include hoglahoo (16), Brourd (12), Drake178 (6), Redspah and jnicol both with (5), Tesla’sDisciple and Jieux both with (2), and Andrewkae, bigbloto, and myself [I solve all of mine to save the sequence, so you must always subtract 1 to get the number of actual solvers] each with (1). Would any of these puzzles make worthy candidates for a new Eterna100.
Shortcomings of the original Benchmark
The Eterna100 were all designed and solved with the standard Vienna folding Algorithm, but there are MANY alternative folding engines to pick from and we have two right here, Vienna2 and NUPACK. The original puzzles weren’t designed with these engines in mind and even though NUPACK was tested against the Eterna100, players always solved these 100 puzzles in Vienna (http://www.eternagame.org/web/playerpuzzles/?skip=50&size=50&sort=solved&search=%3AEterna100) . Along the way there have been a number of ‘variant’ forms of the Eterna100 which have been made and one set of puzzles was specifically made by Brourd to explore this issue, the “Alternate Eterna100” (http://www.eternagame.org/web/playerpuzzles/?size=240&search=Alternate%20Eterna&single=checked&sort=solved). Perhaps his VRNA_2 puzzles should be given consideration.
The original eterna100 were ALL single state puzzles and did not feature switches among their number. More and more it seems that switches are the mainstay of the Lab puzzles here on Eterna, thus switch solving has become an essential skill to have as a member of Eterna...for both Humans and Bots alike. There REALLY should be an ‘Eterna Switch100’.
While single state puzzles were selected to represent certain structural motifs, the criteria for selecting switch puzzles is less obvious. Should we select these puzzles based on whether they contain these motifs found in the original designs? If that is the case then we could simply make switches of the original Eterna100...which I actually have done with several of them (please post if you have also done this!):
Switches based off of Eterna100 Puzzles:
A Most Beautiful Cesspool: http://www.eternagame.org/web/puzzle/8589945/
Cesspool Monster: http://www.eternagame.org/web/puzzle/8589586/
Cesspool Mini: http://www.eternagame.org/web/puzzle/8589200/
Once a Snowflake 2: http://www.eternagame.org/web/puzzle/8567475/
Once a Snowflake 3: http://www.eternagame.org/game/puzzle/8568301/
Flying Gladius takes Flight!: http://www.eternagame.org/web/puzzle/7271687/
However, I feel that a different set of criteria are demanded by switches. Rather than focus on the structures of individual states we should focus on HOW the switch switches: e.g., switches which slide/glide along themselves (including those which do this while maintaining their shape), switches which invert their structural motifs about an axis, switches which have definite symmetry in how they switch, switches which lack any symmetry in how they switch.
It should be stated here that if anyone was looking for a ready population of medium-sized and (usually) asymmetric switches then they need look no further than Malcolm’s Mighty list (http://www.eternagame.org/web/playerpuzzles/?skip=0&size=100&sort=solved&switch=checked&search=Malcolm) which consists of almost 3000 switch puzzles (and it’s growing!).
If we were to select by apparent difficulty (number of solvers), then it would appear that I lead the pack in this regard with (92) 0-solver switches [remember you must subtract 1 from all of my puzzles as I always solve them first]. Other players with 0-solver switches include: wawan151 (37), ElNando888 (18), hoglahoo (7), Eli Fisker (5), Kozilek (3), bigbloto (2), and Andrewkae, Syang, Brourd, Hyphema, Eized, and JR with (1) each.
Another type of puzzle type which was not represented in the original Eterna100 was Lab-style puzzles. And this is the MOST important aspect of the entire Eterna initiative. As players (so far as I am aware) cannot make puzzles of this type then we must refer to the Labs themselves. quantropy has suggested that we use a score function to evaluate Bots and their designs and I like this idea for Lab puzzles. While we are still learning what works best for current Labs, we have MANY Labs which have previously been done and which have scores associated with designs. The scores of these previous designs can become the score against which the Bots are tested, And, as we have synthesized many of these molecules in Lab, we can accurately claim for the EternaLab100, “Designed by Bots, Scored by Nature”. I’m sure Eli Fisker has plenty to say in regard to how to select which Lab puzzles would be included in a Lab-based Eterna100.
Lastly, there are some things the site simply can’t do...YET! None of the folding Engines nor any of the player-tools allow for prediction, design, or manipulation of RNA pseudoknot structures in silico. Similarly (not sure if this counts as a pseudoknot) Holliday-junction-style structures are not permitted at this time either. This is a big shortcoming, but this is a problem which has challenged the entire RNA science community as pseudoknots are notoriously hard to accurately predict... let alone design. However, if ever we could get a model for pseudoknots up and running ...this would be a huge boon for the site. Similarly, we don’t have a system in pace (to my knowledge) for modeling RNA-DNA interactions, nor RNA-protein interactions, though some day we will need to cross that bridge.
There is a lot to discuss here and I am sure I may have missed something. Please comment below with your thought/questions/comments, I’d love to see them :-D
My suggestion for topics at the Eterna 100 summit:
Players have a routine for starting puzzles.
They perform tasks to satisfy the general principle of lowering the MFE.
. Make sure you are in target mode.
. Fill in all base pairs with A-U's.
. Boost hairpin loops.
When a puzzle has lots of hairpins and many loops, mismatches are everywhere.
There must be an algorithm that works through a table of stem structures to reduce the mismatches.
A puzzle that isn't solved with the usual task list becomes difficult.
Players might not remember how to implement a U-U boost or mismatch.
( who can remember "catalyst points"?).
A bot does not have that problem. They remember everything they are told.
When players exhaust their task list, what's left is endless flipping.
sometimes you get lucky, not too often.
@ Gerry: this would be a good time for the bot to suggest the tasks I forgot:)
So, what new tasks can be added to our list?
Only the players who have solved the most difficult puzzles can tell us.
Thanks also to Eli and everyone with some answers to those questions and their perspectives.
One reason I think the bots have a hard time with lab puzzles is that there isn't a target shape. The shape has to be designed by the player/bot. For a bot to do this it would need more programmed instruction. For instance in an ms2 puzzle it needs to know to space out where it puts the ms2 to have room to work with different complimentary bases for the ole-goes and the ms2 to do what the constraints ask.
I think many simple things like this could be programmed into them to make them a better lab bot/solver/designer.
I tried my version of this on the Teslagon puzzle.
I can't ( and won't) compete with a bot when it comes to endlessly flipping bases.
The puzzle overlaps so much it is hard visually to see what to do.
I sequentially moved through the puzzle making every stem GC's and filled in AU to collapse the loops to stems so I could keep track of where I was. As I progressed, I flipped GC's that started to mismatch. With the loops collapsed to stems, the stabilization was quite easy.
A bot's algorithm needs to recognize a potential stem/stem's along it's path. The dot bracket notation available in puzzles would be the reference. Collapsing the loops made things easy for me, but bot's don't "see" so would they have any benefit to collapsing the loops?
- 163 Conversations
- 5 Followers
- 78 Conversations
- 10 Followers
- 219 Conversations
- 11 Followers
- 423 Conversations
- 51 Followers
- 206 Conversations
- 6 Followers
- 172 Conversations
- 11 Followers
- 259 Conversations
- 19 Followers
- 366 Conversations
- 30 Followers
- 168 Conversations
- 9 Followers
- 70 Conversations
- 15 Followers