New Folding Engine Discussion: EternaFoldThreshknots

Hello Eterna Community,

Today the developers released an update to Eterna that adds a new folding engine: EternaFoldThreshknots! :tada: EternaFoldThreshknots was added to address the long computation times players faced in the Pseudoknot Pilot lab with NuPACK as our folding engine. Where NuPACK would take an average of 110 seconds to fold a PK90 solution, EternaFoldThreshknots averages roughly 0.25 seconds. EternaFoldThreshknots also outperforms NuPACK, scoring higher on our correlation analyses of experimental data to predicted structure. Hopefully, this new engine will help our players generate even more interesting sequences in our upcoming Pseudoknot lab.

For players who are interested in the details, EternaFoldThreshknots is based on our existing EternaFold engine. The new engine takes the base pair probability matrix computed by EternaFold and employs a processing algorithm called Threshknots (see this paper for more details) to choose the most likely “mutually maximal probability” base pairs in building a structure. The Threshknots algorithm takes a parameter, theta, that is used to filter base pairs with probabilities below a given cut-off. Low theta values predict lots of pseudoknots but decrease in prediction accuracy. We may tune the theta parameter in response to player feedback; right now we’ve chosen a value that we think balances model accuracy and likelihood of pseudoknot prediction.

A couple of other notes:

  1. The new engine does not currently support free energy calculations. The energy estimates do not currently account for pseudoknots, and are thus likely to be wrong.
  2. The new engine is only available in the upcoming pseudoknot lab puzzle (for now). Because the engine supports this tunable theta parameter, we are waiting to release the engine for standard puzzles until after we’ve stabilized on a standard theta parameter.

If you have any questions about the new engine, or want more details about how it was chosen or implemented, we can discuss more below. Looking forrward to seeing some fancy new RNAs come out of this work!

-Eterna Dev Team

1 Like

EternaFoldThreshknots has three behaviors I’ve not seen in other engines:

  1. Rare GC 1-1 internal loops.

  2. Distant and seemingly arbitrary structure changes caused by a minimal change to the sequence.

  3. Sequences containing long (~7+) G or C repeats sometimes have very few or even no pairs predicted.

Do we know anything about these? If they’re expected, intended, indicative of anything, etc.?

I have run across #2 quite a few times. The cleaner the dot plot the less there are so I assumed it was a pseudoknot in progress due to the murkiness of the dot plot, just not enough for EternaFoldThreshknots to pick up and declare it a pseudoknot. Then again, I might be wrong.

These are all weird!

We have been thinking about an alternative folding method (‘eternafold-hungarian’) that may provide more intuitive results.

Can you provide some sequences and screenshots that illustrate each of the issues? That will help devs like me and @brainbow debug.

Here are 3 examples of long stretches of G and C not pairing, and a GC 1-1 loop. The arbitrary changes are so common I don’t know where to start.

1 GC repeats

GGGAACGACUCGAGUAGAGUCGAAAAAAAUAUAAGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGCGCGCCCUCUCCGCCCCCGCCGCCCUGCGCGCGGGGGGGGGGGGGGGGGGGGGGUAAAGGGAUAUCUAUAGUUCGCUAUAGAUAUCCCAAAAGAAACAACAACAACAAC


2 GC repeats

GGGAACGACUCGAGUAGAGUCGAAAAAAACCCCCCCCCCCCCCCCCGGGGGGGGGGGGGGGGGGGGGGGGGGGCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCAAAGGGAUAUCUAUAGUUCGCUAUAGAUAUCCCAAAAGAAACAACAACAACAAC


3 GC repeats

GGGAACGACUCGAGUAGAGUCGAAAAAAAAAAAAAAAAAAAAAAAAAGGGGGGGGGGCCCCCCCCCCCGCGGGGGGGGGGGGGGGGGGGGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGGGUUAUGAUUUGUUCGCAAAUCAUAACCCAAAAGAAACAACAACAACAAC


4 GC interior loop 84 67

GGGAACGACUCGAGUAGAGUCGAAAAGACGCUAUGCGGAGACUAGUCGUGAAAACGUCUAGUCGAUCUACUUUGAGCAUUGUAGAUCAGAAGUGCUCGAAUCAUCGAAAAGAUGAUGCAUAGCGGAGGGUUAUGAUUUGUUCGCAAAUCAUAACCCAAAAGAAACAACAACAACAAC

1 Like

Screenshots with sequences reconstructed:

5 EFT G & C repeats

top

GGGAACGACUCGAGUAGAGUCGAAAACCCCAUCGCCUGCUCCGCUACCCUAAGAAUCCGCUCGCCACCACCCCCCCCCCCCCCCAAGUGGGGGAGGGGACCCCUCCCCCCCCAAAGAAAGCUCGCAGGGGUAAGGGGUAUUCGUACCCCUUACCCCAAAAGAAACAACAACAACAAC

middle

GGGAACGACUCGAGUAGAGUCGAAAAAAAACACAGGGGCGGGGGCGGGGGGGGGGGGCGGGGGGGGGAACCCAACAACCCCCAACAAGGGGGGGGGCGGGGGGCGGGGCGGGGAAACCCCCAAAAAGGGGUAAGGGGUAUUCGUACCCCUUACCCCAAAAGAAACAACAACAACAAC

bottom

GGGAACGACUCGAGUAGAGUCGAAAAGAGGGCACACCGCGCGCGAACCCCCCCACCCCCCCACCCCCACCACGCGGGGGGCGACCCCCCCCCCCCAGAGAGGGGGGGAGACCCCCCCCCCCCCCCAGGGGUAAGGGGUAUUCGUACCCCUUACCCCAAAAGAAACAACAACAACAAC


6 changes to 44 produces 3 structures

44A

GGGAACGACUCGAGUAGAGUCGAAAAAGAAAGGGGGUGGGGAAAAAAGCCCCACCACCCCCAAAAUUUAAAGGGGAGGGGUGAACAGGGGAAACCCAAAUCACGCCACUCCCCAAAAAAUUUGGUUUAACCCCAAAAAAUUCGAAAAAAAAAAAAAAAAAGAAACAACAACAACAAC

44G

GGGAACGACUCGAGUAGAGUCGAAAAAGAAAGGGGGUGGGGAAGAAAGCCCCACCACCCCCAAAAUUUAAAGGGGAGGGGUGAACAGGGGAAACCCAAAUCACGCCACUCCCCAAAAAAUUUGGUUUAACCCCAAAAAAUUCGAAAAAAAAAAAAAAAAAGAAACAACAACAACAAC

44C

GGGAACGACUCGAGUAGAGUCGAAAAAGAAAGGGGGUGGGGAACAAAGCCCCACCACCCCCAAAAUUUAAAGGGGAGGGGUGAACAGGGGAAACCCAAAUCACGCCACUCCCCAAAAAAUUUGGUUUAACCCCAAAAAAUUCGAAAAAAAAAAAAAAAAAGAAACAACAACAACAAC


7 GC 1-1 loop 109 48

GGGAACGACUCGAGUAGAGUCGAAAAGAAAGAAAAAAAAAAAAUGCGCGCAUUUAAUAAAAAAAAUUAAAUAGUUUUUUUUUUUUUUUUUUUUUUUUUCUCUCAUAGCGCGCUUUUUUAGAGAGAACCCCUAGGGGUACUUCGGUAUUUUUAGGGGAAAAGAAACAACAACAACAAC

1 Like

Thanks, these are super helpful. Can you paste in sequences for the last examples too?

I was curious about how many of the designs that made it through as pseudoknots, had g-quads and i-motifs. That was my original start on this investigation.

However I have been wondering about why some of the designs that the data says are actual pseudoknots, don’t show up in EternaFoldTreshKnot. I decided to do a systematic walkthrough of the designs that JR picked out to be pseudoknots in the Pseudoknot - 50 lab.

Around half of the actual pseudoknots are not predicted by EternaFoldTreshknot:


G-quad or i-motif in lab pseudoknots?

So while it seems NuPack is way too optimistic about there being pseudoknots in general, EternaFoldTreshknot is too pessimistic.

A thing I have been doing as of late when looking for pseudoknots, I’m checking if a pseudoknot is also predicted in NuPack, if I think I have a promising pseudoknot in EternaFoldTreshknot.

If NuPack was faster with its predictions, I would check all my pseudoknots there first and then double check with EternaFoldTreshknot afterwards.

1 Like

@Eli_Fisker Depending on your use case, e.g. pseudo-knot design, I find it useful to have a “pessimistic” algorithm as it may tend to give fewer false positives. On the other hand if you are interested in pseudo-knot detection, you may tolerate more false positives if it helps to eliminate false negatives. As you say, if it passes both filters it may be more likely to be a real pseudo-knot in this lab. I’ve been trying a base-pairing threshold design strategy myself but I’m unclear if it can properly distinguish between a pseudo-knot and a switch in some cases.

1 Like

@jandersonlee, you describe the dilemma really well. It captures why I doublecheck NuPack. Because I’m interested in pseudoknot detection. I use g-quads or i-motifs being nearby as a third criteria that I like to be fulfilled, before I accept that there is a potential pseudoknot. Unless the pseudoknot itself looks really good on its own.

I have also ended up shifting my approach from genome browsing to gene browsing. So now I’m instead browsing the coding sequence specifically. Individual mRNA’s:

My fragmentation spreadsheet part:

On the switch part, a good deal of the natural detected pseudoknots are actually riboswitches.

Thanks so much for these sequences! It’s very helpful for our debugging efforts. I’ll address #6 here.

Rachael Kretsch (Das lab researcher) and I looked at the structural changes introduced by the change in base 44. To start, here’s the structures predicted by eternafold+threshknot:

44A threshknot 0.2
.....((((((.....)))))).........((((((((((.......))))))).)))((((.((((...((((((((((((...(((....)))...)))).)).))))))...)))))))).....................................................
44G threshknot 0.2
.....((((((.....)))))).........((((((((((.......))))))).)))((...((((...((((((((((((...(((....)))...)))).)).))))))...))))[[)).........]]..........................................
44C threshknot 0.2
.....((((((.....)))))).........((((((((((.......))))))).)))((.(.((((...((((((((((((...(((....)))...)))).)).))))))...)))))[)).........]...........................................

The apparent difference between 44-G and 44-C comes from the pruning of single base pair helices. The predicted pseudoknot changes from a 2bp helix to a 1bp helix with a corresponding 1bp helix at 63-121. As to why the 44-G,C structures look different from 44A, both the predicted pairs for the 121,122 nucleotides (62,63 or 134,135) are very close probabilities. I’ve attached the BPP
plots below. The plots show that these pairs are both equally likely, and Eternafold’s predictions change slightly depending on the whole sequence. It’s appears like a radical change, but it’s just a slight shift in pair probability ranking.



Its a classic example of the MFE shape not being very different from other possibilities in terms of free energy, hence a small change can flip the structure to a new/different MFE folding.

Yep - the unique thing here is that because it’s operating on the ensemble pairing probabilities rather than picking out a structure based on the sums of its component energies, a change in one substructure can actually affect another substructure. This does break some of the assumptions many of us are used to, so requires thinking about the problem a bit differently.

I’ve got an optimization strategy I call “polishing” that tries to remove some of the more egregious alternatives by examining the base pairing data and adjusting the sequence to reduce conflicts. It does so somewhat indirectly using a “scoring function” based on one used by Nando in some old labs and by looking at bases that seem to have conflicts due to lower scores. Essentially it tries to raise the pairing probability for pairs closer to 1.0 and for unpaired bases closer to 0.0. I’ve got about 400 submissions that use that metric so hopefully we’ll see if it helps or not. Alas it has a tendency to turn designs into “christmas trees” (GC/CG) if run too long.

@jandersonlee Have you had a chance to look at the pilot results to calculate how well the optimization strategy worked? Curious to see your analysis at some point.

@brainbow EternaFoldThreshknot pseudoknot depiction is “right-handed”, same as NuPACK, meaning the higher numbered base pairs get the banjo strings. Was this an intentional decision or a feature already defined in the Threshknot algorithm?

@DigitalEmbrace Actually, the “right-handedness” is not coming from the model (or at least, not primarily), it’s coming from the internals of the Eterna codebase. When we get a structure back from a folding engine, we just turn that into a list of what bases are paired to what other bases (in the case of threahknots, it’s actually never a dot bracket - we directly set pairing partners based on dot plot data, though IIRC there is some implicit biases in the way the algorithm works when eg different mutually exclusive pairs are considered equivalently likely or conflicting with maximal likelyhood of already-processed bases). When that is displayed or turned back into a dot bracket, the first pairs encountered (starting from the 5’ end) are always represented as “normal” pairs.

I didn’t use this strategy on the pilot designs and have not checked it on them to see how well it might perform. What I have seen from the pilot designs results suggests that it might be trying to hard to look for “balanced” knots (i.e. 50% probability of each side). In a lot of cases however it seems that the stem or stems from one side might heavily outweigh the other and yet the knot may still form. For example if there are 10 base pairs on one side of the knot and only 3 base pairs on the other you would not expect both stems to show up in the dotplot at 50% probability. I have been puzzling over how to detect and compensate for that but have not come up with a solution yet.

@jandersonlee I know you have been playing around with the theta setting in your ArcKnot tool. Do you have an impression how well the current in-game theta is doing?

My impression from loading pilot winners into round 1 is that the theta is set about right. EternafoldThreshknot gets close to ground truth but isn’t always there, which means the algorithm is slightly heavy on the discrimination scale. I’ve been able to make mutations to the sequence that result in EfoldThresh finding the target structure. So only ever so slightly leaning towards discrimination, and I’d rather be slightly more discriminating than slightly less.

The theta feels pretty dialed in to me. but want to check with other players on their experience before we begin OpenKnot round 2.

@DigitalEmbrace If theta is the threshold, my answer would be: it depends. I’m still wrestling with a scoring function which is in some ways tied to the threshold.

When you have a fairly balance knot, with a similar number of bases one both hands, the threshold could be high, even 0.25 or above:

…(((((…[[[[[)))))…]]]]]…

However when you have a small number of bases folding back on a larger structure, the threshold will need to be lower to capture it. I don’t have a good feel at the moment how low that should/could be. I’m currently unable to load the lab designs page (Unable to Load Solutions) to seek out an example, but it could be something like:

…(((((…(((((…(((…))).[[[…)))))…)))))…]]]…

Here there are 10 pairs on one hand of the knot and 3 pairs on the other hand, plus 3 pairs on a stem that is internal to the knot but not contributing to its knottedness. The 10 pairs (two 5-stems) will tend to form more strongly than the three pair stem leading to an imbalance in the base pairing probabilities computed by most folding engines.

In this case, you will need a lower threshold to detect the knot.

As I say, I cannot find a more specific example at the moment as the lab won’t load for me.