Video 8-4: Refined energy model, Zuker algorithm

0:02 I'll describe the more general algorithm again but with a a more graphical syntax and then we'll leave it at that. Um the maximum matching unlike the general case for outer planer uh or pseudonaut free structures already gives you a reasonable structure is is much better than this original one where the numbers were essentially predetermined and everything turns into a a clump. Uh here this is sensible but people observed that it's still uh counting the num total number of pairs is not as good as counting pair stackings and we can extend the dynamic programming. Um I was waving my hands already on how to do that. Um for going further and for the extensions that people then further did they often went to a more uh pictographic way of showing DP recursions and I I think this is just in in a way beautiful in its own right. So maybe it's useful to just show you this as an example. Maybe it helps you think about such problems.

1:13 Uh the specific recursion maybe don't don't worry about that for now. Um just the syntax is you're looking at a substructure from some some position to some other position. It may have some constraints like in this case the the wiggly thing means there has to be a pair. So the outermost two elements are paired whereas uh what's inside here we don't know.

1:40 And so we say the the value of this substructure is the best of so it's minimization here we used to maximize minim minimum would be for free energy uh it's the best of certain uh possible options you have either it could be that there's no further pairs in this range the white area means no more pairs or it could be there is a pair then you find the outermost most inner pair. The rest is white. And here you recurse. This obviously has the same shape as this. So you know what to do, right? In a DP recurrence, you would have some uh this would have some name and some parameters I J. And then this would be the same name with appropriately adjusted I J. So some new parameters I prime, J prime. uh or maybe um you say there's a cut point K where uh these these dashed lines mean I don't commit yet to what's happening here between the outermost pairs could be anything um yeah could be paired or not uh but I know that the substructure so this part is white which means there's more pairs in here or more pairs in here maybe but nothing between them okay so it's roughly clear Um and with that you can express uh what I tried to describe earlier. We need two uh uh mushial recursive constructions. Uh we need one where we know that the outermost bases are paired and one where the outermost bases um are not paired or we don't know. It doesn't actually matter because we determine the best possible structure.

3:29 If if I had the choice to add another pair, that's always going to be better. So I think it doesn't matter if you restrict if you here say the semantic is there cannot be the pair J or whether you say it's not fixed. It could be there or could not be there. I think it doesn't matter.

3:47 Okay. So you could do um counting the number of of of stackings in the following way. If you know the outermost pair is there either there's nothing further in there or you find the next inside uh or you do the bifurcation and for this part you again you have the option to put the pair there and recurse or have unpaired I or J or further bifurcate.

4:18 It's not an ambiguous uh decomposition but it's good enough for minimization. You see here that if you have several ways to bifurcate, you may do this in any order and it's not unique but doesn't matter for minimization.

4:39 there's complexity doesn't change by this uh if you implement it well. Now remember um what this looked like here. There were all these lovely um numbers shown. Where do these come from? Obviously they're not simply counting pairs etc. but rather uh they have a a chemical model in mind that's known as the Turner model because uh this guy owns some lab and they've done tons of experiments uh to figure out for all sorts of small substructures what their contribution to the overall stability of a molecule is. Uh so even counting these stackings is still um a relatively rough approximation.

5:29 um it depends on the exact basis. So the the bonds between GC are much stronger than uh AU and GU is even weaker. Um also I've showed this in the in the tool earlier that sometimes adding another base in the unpaired part changes the contribution to to stabilization. Um and even what's in the hairpin loop can influence things. So uh as a culmination of a lot of lab work they published for all sorts of structures the corresponding energy contributions long big tables that we don't want to go through. I just want to conceptually show how they work and I think it maps nicely to again the graph representation. In a way you could say they give an energy contribution to each of these faces in in the planer graph. So for example, one for this blue part which would be a destabilization because this is a bulge and the green one is a stacked pair. So that would be stabilizing.

6:35 Um and they have lots of tables that tell you depending on what the bases there are and how big the bulges are and how big these multiloops are and all for various combinations of things they tell you what the energy value is the contribution to free energy. So in theory all you have to do is decompose uh a large structure into all these possible faces.

7:03 If you do this directly, it actually doesn't work because uh think about this this huge face here where I put the text in. You could have as many pairs inside there as you want. And uh if you want to optimize where they need to go in a dynamic programming these are a lot of variables. So that would drive up the running time uh essentially beyond polomial.

7:32 So what people do um is you restrict it to two pairs inside. So you have this wiggly line outside and you allow two more wiggly lines inside. If it's more than that, you do some uristic and say, I'm splitting off one and there's a an additive function that you can deal with without specifying them already. And I think the energy models also aren't so precise for these big structures. They only work well for the small small uh faces. So uh with that um you get essentially the same kind of recursion as you had here. Instead of having more of these inside you would use this rule and give a a general contribution to this uh outer outer loop.

8:34 So that should be that's called uh suker's algorithm. um one of one of the other people involved also with the the paper is here but it's by and large the same dynamic programming pro uh algorithm.

8:48 My understanding is that's essentially also what Eterna uses. So this is still state-of-the-art even though uh the papers are 20 years old.