Video 8-3: Pseudoknot-free secondary structures, Nussinov algorithm

0:02 So what what do you do if a problem is too hard? You restrict it to some uh special case. And indeed in this case it's even biologically helpful to to restrict the problem a bit further. And the reason is basically in the pictures that we've seen before. If you look at these roadkill diagrams, what do you not see uh are crossing lines compare uh corresponding to the uh pairs or the backbone. It just runs nicely through here. And if if you want to say it in other terms, it's a planer graph and it's in a way even more restrictive. So first of all, it seems reasonable that we don't need crossings from the one example I've shown you. Uh and indeed it's uh it's true that most pairs that you find in real structures don't have crossings. It's also true that whenever in biology there's a rule there's some counter examples. Uh so sometimes um crossing structures exist but the crossing only involves few pairs and so we still get a reasonable uh information about the overall structure if we ignore the crossing pairs and focus on the getting the other ones right.

1:22 Now it turns out the uh the right formulization here really is an outer planer graph if you think about the backbone as part of the graph. uh outer planer means there's no crossings. The edges never cross. There's a way to draw the graph so that uh you can align the vertices. Edges are straight lines. They never cross. Straight line is not important but they never cross. Plus the outer planer means all the vertices are on are adjacent to one face. And in this case we can always draw it that it is the outer phase the uh the part of the space that extends to infinity whereas um so I don't know maybe let me sketch this a bit more. Here's our vertices uh in an outer planer graph. I can connect these inside here. It's in principle also allowed to do more than a matching even though we will never have that here. I can have things nested, but I can't have an edge like this.

2:25 That's not allowed because it crosses another edge. And outer planer seems to be a good match for the structures that occur. And it has another good feature. It makes the whole thing tractable. Um the opposite. If you cannot draw a graph a structure in the graph form like this, then it's called a pseudonoded structure. It's a pseudo knot because it isn't actually a knot in the sense of topology. It's just a twisted around. Um, for example, you could have structure like this where you have pairs here and you have pairs here. Let me draw it a bit bit more careful. Maybe you have here and here you have uh bonds. Then this you cannot draw as an outer plan. There's vertices inside here that would be cut off from the outer face, but it's still not a real knot. It's a one nice line. So these are pseudo knots, but for outer planer, we'll ignore those. So we'll focus on pseudonaut free structures.

3:38 [snorts] There's biological motivation for that as well. Um, first of all, the structure is in 3D. If you restrict it to 2D, it's not so far away hopefully. Uh, it's also a useful coarse graining of the structure because it focuses you on these uh long stems which tend to be the most dominant feature in in stabilizing the molecule. Anyways, uh this coarse graining might also remember the video hint you better at the pathway to get to that folding as opposed to just find showing the final result. And the last point of course for for us is useful if we want algorithms that bind the structure then we need to pick a restriction of the problem where we can give such algorithms.

4:30 So in a way I should say this is this is so widely accepted that if you in general um look for RNA secondary structures people implicitly mean pseudonut free you have to explicitly include pseudonuts uh in the language because so widely used and so widely accepted that you can't deal with pseudonuts in general but uh people will understand pseudonut free as the default >> [snorts] >> Let's study uh these kind of represent these these kind of structures a bit more. There's the way um the roadkill diagrams we had before. The way also Eterna draws the molecules. Um biologists biologists give these different kind of shapes uh a name and maybe it's worth to point this out once. So there's there's the stems that we already had which is just these uh these stacked pairs the the most important feature. Then there's HL here this hair pins where you turn around. Uh these look boring because they're not paired but for the biologists these are the interesting regions because those tend to be the ones that stick out and that can do a function. So often times in say in a tRNA these uh bases in the hairpin are the ones that are highly preserved between different species because they might do the translation from genetic code to uh protein or amino acid. Whereas uh for the rest for the stems uh we don't care so much what letters make the stem as long as they stabilize it. And so often here you find mutations as long as they're so that the partner is mutated correspondingly.

6:23 Uh then there's two other three other features. This bulges that's the B when you have a stem interrupted on one side you can have interior loops that's a bulge on both sides. And the last one is this multiloop where you have more than one uh pair reachable from this. In terms of the graph uh planer graph uh terminology, these are just the faces of the graph. Uh right, if you if you draw it like this, then the edges uh separate the plane into several faces. There's the outer face and then there's these small faces of the stack pairs. There's the bigger faces of these multiloops and so on and so forth. Okay. Um I don't care too much about these uh these names, but if you read in biology sources, they often refer to these names. Now imagine you take this picture and you pull the backbone onto a circle. That means you pull away these uh so these all need to move a bit outwards so that they follow the the line here of the circle. That means these um this outermost stem is corresponding to these uh maybe I could use some color. This stem corresponds to these pairs, right? And you can work out where the others go in that representation. It's even more obvious that this is outer planer.

7:58 That's the way people draw outer planer graphs. Uh if you want to highlight that they're outer planer because you see obviously all vertices are adjacent to the outer face and no crossings for the edges.

8:15 I consider this as an intermediate stage because now if you have the circle, it's not actually closed, right? Because this is a linear structure. Let's take the circle and pull it straight. Then you get to this picture. Again, the same structure. And now you have these arcs on top. And again, it's outer planer if and only if you could draw it as a line with non-intersecting arcs all on one side of the line. And hopefully you can visually see how these all correspond to the same structure.

8:48 That brings me to the last representation which looks very innocent. And there it is. Um, from this linear arrangement, very easy to see. You can represent edges by opening and closing parenthesis. And the other basis just as dots for unpaired. And then this string of uh opening, closing, and dot that's completely describing the structure. So if you want to work in a computer with these structures, clearly that's the way to go, right? Then it's just a string. um much less hassle than dealing with these pictures. But uh biologists of course prefer those because they are closer to the structure in threedimensional uh space.

9:36 Um yeah, also note that uh precisely the fact that these uh arcs are all above the line and don't cross means that you just have to find the corresponding parenthesis. the matching parenthesis is your partner in the in the matching. [snorts] Okay.

9:56 Now, you could do all sorts of combinatorics with this. You could say uh we can count how many structures there are. Uh you could find out that while there's clearly four to the n different sequences, there's a good deal fewer secondary structures. So, a good hint that um there's always going to be exponentially many sequences for the same structure and so on and so forth. uh we're not going to go there even though it's it's um fun stuff. Let's come back to algorithms and try to predict uh a good structure solving our original problem. Um funnily enough, the first algorithm that was somewhat useful for RNA structure prediction, Nusenov's algorithm did what I originally said is useless. Namely, it just maximizes the number of pairs. But it maximizes the number of pairs in pseudonut free structures. So these outer planer graphs and there of course uh you can still solve maximum matching maximum matching in polinomial time. Uh but it's restricted to the graph being out of planer. So I don't know if there's a an obvious second algorithm apart from the one that I'm I'm going to show you. I will come back to the counting pair stackings because that was the more realistic thing. Um, but I think historically that's correct to say that the algorithm first just counted the number of valid pairs.

11:24 Any thoughts how you would do this? So think about what you're given as input is the the sequence of bases just the letters and you're trying to find the best such uh balanced parenthesis string and you're maximizing the number of of parenthesis uh how could you possibly get started here or what kind of algorithm design pattern might be useful I'm already hinting at that it's going to be polomial time otherwise we wouldn't be talking about it further.

12:10 I mean, whenever a problem looks harder than greedy, it's probably going to be dynamic programming. No. Um and indeed um the good thing about these these bounce parenthesis strings is suppose I somehow figured out that this this pair of parenthesis is matching and I want to have this one right so there's uh this pair what I do inside here and what I do outside here it's going to be independent they can't there can't be any crossings. So, whatever pairs I uh the the maximum number of pairs I can throw into this pink part that crosses the arc I I decided to put it's going to be independent of what I do inside here because they can cross. Uh so there's a natural decomposition in a bit more structured terms. Uh we'll come to that. um decomposability is is the key thing for a dynamic program. I guess from how I showed it is already suggestive that you want to have subsequences or substrings um as your sub problems. So formally we'll have dig to be the maximum number of valid pairs that you can possibly squeeze in any pseudonut free structure for this subrange of your RNA. And by solving this for the whole thing, we'll make our way to the solution for r0n.

13:51 And um if you if you think about how so I guess the picture is drawn in a way like you add one more base or so. If you have a a range I to J what could the inner part look like? One option is there is a a pair I J and there's maybe a pair inside but certainly I and J are paired or I could be unpaired or J could be unpaired and then whatever comes inside recursively resolve it or we have some cut point where everything to the left and everything to the right is a separate structure that don't interfere. That's all options in a way. If you want to see why it's exhaustive, you look at what I and J do. Either they're paired with each other or one of them is not paired at all or they're both paired but not with each other. Right?

14:51 I think this is a bit misleading that I is paired with essentially K minus one and J with K plus one. So this is not needed. There's just a there could be a longer stretch, right? Uh I and J are paired with something So there's going to be some some part here and then there's an arbitrarily long part in between that doesn't matter as long as I can find one cut point K. So in the recursive programming um recur rec recurrence I have the number of pairs I can form is is nothing zero if I'm too close if I'm on a tiny piece of the RNA and otherwise it's the best among those four options. For the first one, I have to check if I can form the pair between I and J. And note uh I stole the pictures from uh one of the books I mentioned in the website where they have I and J inclusive.

15:41 But to be consistent with the rest of the module, I used here R I inclusive J exclusive. So this is uh the pair we would want to make is between RA and RJ minus one. uh I can add another pair if these are in the canonical base pairs one of the six allowed combinations otherwise no um then I go to the recursively computed structure uh between those and for this bifurcation part I have a maximization over all possible cut points uh so clearly um quadratic space is sufficient to store all the sub problems and because of this maximization Here I have another linear factor in in the running time if I don't try to be uh smarter. Um because this algorithm and versions of it are so much used in practice people try a lot of tricks to speed up at least for typical cases uh what happens and um often times you can remember where what the cut point cut points were in the smaller structures and keep a list of those. So you may not have to iterate through all of them each time.

16:55 Uh there's there's a few tricks you can play. Uh but by and large you're stuck with some higher polomial running time. So this is is indeed tricky to do with very large molecules. [snorts] Okay. Uh what's left is number one to get this to the more realistic model of uh counting uh pair stackings instead of pairs. Uh I have a separate slide but I think it's it's actually easier to do with these pictures. Um, it's not at all difficult to count the pair stackings instead of pairs because all you have to check is whether there's a way to close a pair here and also have this pair there. Now, uh, the way I set up the recursion here, we don't know in the substructure what we did. So, we have to remember an extra bit if you like whether we close the outermost uh I J minus one whether those are paired or not but if you know that then you could say one option is I close the pair from I to J and the one just inside also needs to be closed that's one option then I can add one one stacking and in all other options I don't get a plus