Constrained folding to give correct "delta" in puzzles with dont cares

[rhiju]

Update useful for, e.g., ribosome puzzles of the week that need to be solvable. The 'delta' energy, introduced by @luxaritas, gives generally very useful guidance to players (we are trying to make it zero), but currently it doesn't go to zero upon solution of puzzles with "don't care" regions.

delta = MFE - target energy

For the target energy we shouldn't just stick the target secondary structure into the energy model. We should allow any dont care regions to 'relax'. Most packages have the ability to find the MFE structure given the target base pairs, target unfolded bases, while finding MFE for any specified dont-cares regions, through a 'constrained folding' option.

This issue would be resolved by:

• [ ] Use a recent release of Vienna 2.x to replace the current early release of Vienna 2. The newer releases have constrained folding
• [ ] Use the recent update of LinearFold that allows constrainted folding.
• [ ] NUPACK has constrained folding too, I think.
• [ ] We'd probably need to compute constrained folding 'classic' Vienna 1.8.5 folding through appropriate command-line updates into a recent release of Vienna 2.x.

@everyday847 @luxaritas

As a separate note, emulating other Vienna1 functions with Vienna 2.x would have the added benefit of reducing the number of external libraries that we'd need to compile and link in to EternaJS. We could imagine deprecating ViennaLib. Probably that should be a different issue/PR.

[rhiju]

Test puzzle could be 23S rRNA PTC puzzle of the week, which requires dont_care regions (specified as "structure_constrained_bases":[0,7, 15,16, 21,31, 34,69, 71,73, 81,83, 85,90, 93,104, 106,115, 119,147, 152,156, 159,161, 166,168, 171,233, 236,238, 242,267, 271,272, 276,283]) to be solvable.

On the dev server: http://eternadev.org/game/puzzle/9386253/ http://eternadev.org/node/9386253/edit

On the production server: https://eternagame.org/game/puzzle/9612426/ https://eternagame.org/node/9612426/edit

[everyday847]

I'm currently working on a Vienna2.1.9 => Vienna2.2.0 update, which is the minimum increment necessary to getting constrained folding in. It is not terrible so far.

[everyday847]

It's also not great. They totally change API between those two versions so I am basically going to have to rewrite the patch from scratch.

[luxaritas]

Is the idea that we could get Vienna1 behavior just by providing the 1995 Turner parameters as opposed to 1998? Or is there something more? If that's all it should be relatively easy to test right?

[luxaritas]

As I'm thinking of it: a potential downfall here is that these "don't care" regions also double as user-designable regions. Especially if it is an open-ended problem (like OpenTB), it would likely be desirable to have the delta reflect the difference between the target structure (as modified by the user) and the native (iirc it doesn't do this either, I think it uses the default secondary structure). I'm not sure what the best way is to handle this... A setting? What should the default be? Is there some "common-sense" default we can provide per puzzle? Something else?

[Omei]

The purpose of the "don't care" designation is really quite different between creating switches (essentially from scratch) and modifying the ribosome (essentially making tweaks).

When designing from scratch, the only reason for the "don't cares". was to make the placement of aptamers easier for the code to handle. That is, Nando could lock the aptamer structures in a fixed location, rather than making the game find them and adjust the energy calculations accordingly. Ideally, every position would have been unconstrained (as it was for OpenTB) and there would have been no reason for the introduction of any "don't care" construct.

For the ribosome challenge, we care very much about the structure at each position. I was the one who decided to re-purpose the don't care when I was trying to figure out how best to turn the crystal structures into a playable lab puzzle. It was immediately obvious that none of our folding engines was going to allow the puzzles to be "solved". The first thing Andy and I tried was to modify the secondary structure string to something that could be solved. That seemed like a plausible way to treat the 5S. But the 16S and 23S wee way to complex to figure out how to do that. So I started adding "don't care" regions to make the puzzle solvable. My Intent was to say "Don't bother trying to change these, because they won't help solve the local structure."

Both uses are essentially stopgap measures. I don't think we need to unify them; we need to obsolete the need for them.