Video 8-2: RNA secondary structure

0:03 Let's now translate what we've seen from the biology side to a mathematical model of this. And uh as before, we'll essentially assume the RNA is a string. It has it has a direction. Uh I don't know if I stressed this all that much when we talked about DNA and and genomes. Um the molecules have a direction. there's a distinct fivep prime start and a threep prime end. The the sugar backbone is not symmetric. So you can't just say I'm I'm going to read this string left to right or right to left. There's a direction. Um that will be somewhat more important later on. the um sequence which we think of as the input that's the thing we can easily get because there's these uh high throughput uh sequencing techniques that can read off from at least from DNA uh in uh at low cost and high speed lots of lots of sequences at least short chunks and because RNA is directly copied from the DNA you can get that string very easily For DNA, you may remember that there was T for thamine instead of U for uricil.

1:19 So there's a different base in RNA, but it's chemically similar. So the name is kind of further away than the chemical structure as far as I understand. This is what we get as input. What we'd like to predict is the three-dimensional structure, but that seems hard. Um so instead what we do is uh focus on this secondary structure and this you should think of uh just some pairs. By and large it's a good a good enough approximation that some of the bases in the RNA hold so that they are close together in space and they form a hydrogen bond a chemical bond between the the bases. So the abstract representation for the three-dimensional structure or the our approximation to that is just a a set of pairs. They should be uh disjoint. So every base can be part of is exactly one pair or at most one pair I guess. Um and there's a further restriction that they can't be too close to each other in a way. Um, if there's pairs here and here, you need a few in between for them to be uh for them to form a pair. Otherwise, the backbone would have to uh do too sharp a turn.

2:50 we'll also require that the bases that we consider a pair are actually able to form a bond. And that depends on this uh the basis that they have there. Um like in DNA there's the the pairs C and G are complimentary. So they're oppositely charged in a way. This is more like the uh hydrogen and uh hydroxal groups um match. They're also charged I guess. So you could say it's two magnets. Uh so C and G can can form a bond and A and U can form a bond. That's the same as in DNA. That's the complimentarianity that we had in DNA as well. Um but it turns out that G and U can also form a slightly weaker bond. These are often present in these structures as well. So it's a bit less clean in a way. Uh so these these six pairs we call the canonical base pairs. They tend to be stabilizing. If they are close together, they attract each other and they stabilize the structure.

3:51 Whereas other attempts to bring other bases together rather uh you get a uh a force to push them away from each other. Okay. So first attempt if these are stabilizing structure, one first attempt to uh compute a good structure for an RNA or a likely structure for an RNA would be to maximize the number of bases we can pair. Okay.

4:21 Uh before I move on, can you think about what computational problem that would correspond to? So um think of the backbone as this linear arrangement. Then there's all the bases lined up here and there I'm just drawing them as dots but really of course they're one of the four letters. Okay, my example is too big. So really is a c a g u a whatever.

4:56 Now I'm asking to get the maximum number of pairs possible. How would you model this? thought. >> Yeah. Yeah. Uh it's hard to hide in this room. So, >> one option um >> Uh yeah, maybe uh think of it more um more brute forcy for now. Uh, for example, every base with a C could pair with a base with a G. So, for example, these that's, uh, in in gray, I'm drawing a hypothetical pair. Okay, this is a possible pair. I'm not committing to that yet. But then, uh, there's another G here. So, I get another possible pair. I may not get a pair between this A and U because they're too close. But, by and large, that's it, right? So any other these I would get. Now remember um that the pairs have to be disjoint. So um if you think about this as a graph and forget the backbone edges then it's just a matching and indeed I mean uh is a maximum matching.

6:23 is not trivial to solve but we could do it in polomial time even in general graphs and so you could say problem solved here it's even if you ignore um if you ignore these minimum hairpin loops it's even a trivial problem because uh some of these pairs in particular C and A they only have one other base that they like to to pair with. So if you greedily form all the pairs with CG and AU first until you run out of bases for those and then do whatever is left as GU pairs, that's going to be the best possible. Um because of the minimum hairpin length, it's a little less obvious if that's the best possible because there's some maybe you end up in a in a uh um somehow you end up trapped with pairs that are too close. But you could just model the thing as a graph and then all the edges that are in the graph are possible bonds and you pick a maximum matching.

7:29 Okay. Now unfortunately this is uh is pretty useless. Um for one that's why I spelled out this halfbroken algorithm which I guess is is not okay to just ignore this this requirement of the minimum hair. If you assume this, then the result just tells you the number of pairs is essentially fixed by the the letters. And so there's going to be gazillions of different solutions all with the same quality but very different structure. And what's more, um, if you think about this again, a bond, a pair means that you have to somehow contort in space the structure to be close. When the two pair two bases are paired, they should come close together in space. If you do a an unrestricted matching of this type, it might just all force the whole thing to be in one place. That's not going to work in in finite dimensions. Uh so this is in a way too unrestricted.

8:32 Uh we can't allow arbitrary uh pairs. But the thing is any specific pair in isolation is fair to allow. Apart from these this minimum distance, it's quite possible that you have the some specific pair from far away. It's just that once that you have done some pairs, some others become less likely. So problem is a bit more interesting than that.

9:02 And um to get a bit of a feeling what is more realistic, let's play a game. I'll explain in a second where this comes from and why someone set out to make a game like this. Uh what you see here is one long chain of RNA. At the moment, uh, it's totally unpaired because it is consists essentially all of A's with a few, uh, C's and G's sprinkled in. And you can now change what it looks like by adding a few more. Yeah, the sound is very useful. Um, and remember that uh, C and G attract each other.

9:57 So, if you add enough of these, it starts to form into some different shape. Now, let me add a few others. Oh, it's very slow. Poor laptop.

10:15 I'm actually clicking, but okay. So, you see, I've added a bunch of of uh G's and C's that should attract each other, but if you space them out too much, they don't. Okay. Uh you need to bring several in a row together for that to work. And now, you may also note uh notice these numbers that appear here in these in these regions. Um the negative numbers, the green ones, these are stabilizing because they're intended to mean free energy, which is uh how stable is the structure. Um the lower the free energy, the less it wiggles around and the more stable it is. So you see these these huge unpaired loops here as similar here. They have a positive contribution which means unstable. Whereas these guys here nested between two adjacent pairs. They're stabilizing a lot. Uh then there's fun things like sometimes um if you put a a G here, watch the number here. It's 479.

11:20 And now it suddenly went down. Even though I didn't close a pair, nothing changed in the uh the layout, but this number went down because sometimes this G and this A, they still attract each other a little bit. Um even though they don't form a pair. So you already see um it's not always quite as clean.

11:53 And you can also form au pairs. And there's funny things happening here as well. Uh watch these two numbers. If I flip around this pair, they both get worse. So there's things like um AU pairs, they like to be alternating, whereas the GC pairs, they like to be aligned. So there's there's a lot happening in the chemistry that's not shown at this level level of abstraction. Okay.

12:20 Fine. How how are we going to make sense of this? Um the first order of abstraction is the stabilizing effect by and large comes from these adjacent pairs. They had the biggest effect. Remember at the very beginning I put just a few green and blue and red on opposite sides and they immediately found each other. Um so by and large that's the biggest effect. Okay. What about this this game? Uh it's called Eterna, cheap pun. Uh it's some collaboration of of CMU and Stanford. Um it's been running for a long time, which is impressive if you think about how shortlived some uh projects in science can be. Is also fairly well done for an academic project, I would say. They hired people to do the programming, I guess. [snorts] Um, what you have to do in the game is actually uh slightly different than what I showed you. Maybe I'll show you the the actual game.

13:22 In the game itself, you're given a target structure. This is what you're supposed to build. And now you have to set the basis in such a way so that this is the outcome. And often times that's the more um applied use or the medical use. you know roughly what function this molecule should play in some cell and so the structure dictates that but you don't know how to make a chain so that it folds into exactly that that structure and the game says uh maybe you can do it. H it's also an attempt to make um the database grow in that they uh they crowdsource designing interesting molecules and once in a while when they have interesting candidates they synthesize them in the lab and then determine the structure to then check if uh they can improve the models. Of course this is a simulation. So also the structure that you see there it's flat and everything it's not going to be the real thing. They try to get closer to a more realistic model with the same same kind of engine. It's there to design molecules that might work and also while you check whether they work you get better data about the models to predict.

14:42 Uh it's quite fun to play. So uh if you want to help science you can yeah give it a go. It gets hard very quickly. What it teaches us is these two things. Number one, mostly these um these these uh neighboring pairs seem to stabilize molecules.

15:03 And also uh it's a pretty good approximation to draw the whole molecule in the 2D plane as opposed to the three-dimensional structure that it really has. Um and so that's what people usually work with. Uh, I love this this tomium I learned from from a video the roadkill diagrams because you run over the the RNA with some truck and then that's what's left. Uh, this is the same same structure uh taken from Wikipedia at least. I hope they're right. There's some parts here that are not actual basis but they're labeled with the function that they fulfill. Uh, but here you see um, for example here this this endpoint that's the the yellow and purple part. Whenever you have these uh these pairs of neighboring um bonds, they turn into something that looks suspiciously like DNA, the double helix. And in fact, that's very similar indeed what happens in DNA. Turns out the geometry is slightly bit different, but uh if you if you measure the angles and so on. Um but it does have this this helix shape. It always turns in a certain direction. And if you have two complimentary strands that run in opposite ends, they can nicely uh cork screw together. And that's what comes out of these ladders that we draw flat.

16:27 That's why they're stabilizing because they tend to have a whole a whole region forms into these twisted shapes. Okay. So roadkill diagrams and these neighboring pairs that seems to be the thing. Adjacent pairs give the main stabilizing effect. Um in biology people call these stacked pairs. Uh don't call don't ask me why stacked. I guess in the 3D structure maybe it's a they they slot into each other in a in that sense. um the whole confirmation of several of the such uh stacked pairs is then called a stem. I guess that it's maybe um bit more pneummonic [snorts] and again in 3D they look a bit like the double helix of DNA.

17:20 Uh finally and I'm I have to admit I don't fully understand why this seems to only work with complimentary stems. So complimentary strands, if one strand goes here and the other goes in the opposite direction and they're complimentary. If they go parallel, it doesn't seem to work. The angles in the the little the bases here, that's these are the the hexagons, they don't seem to come out at the right angle. So you'll have in and out, right? This this strand goes in one direction, the other goes in the other. Then they can slot together. If they both go parallel, it doesn't work. Curious, but seems seems to be a thing.

18:08 So, how can we model this? Again, let's get rid of most of the details for now and rather just maximize these stacked pairs. So, here's I guess the drawing is is the clearest. Um, again, I'm assuming this goes in in one direction and out in the other. So, these are complimentary and opposite directions. And then I have here a bunch of pairs, I'm only going to count pairs of pairs that are adjacent. And because it only works with complimentary strands that go in opposite directions, it means if I have I and J here, I'm going to have I + one and J minus one here. So I can count these in terms of formulas for the the pairs of indices in a very simple way.

18:59 So that's the uh the second version of this of this problem. Our second attempt given the structure the sequence. Let's find a structure that maximizes the number of these pair stackings.

19:13 Okay. Unfortunately that's a hard problem. It it went from maximum matching relatively easy poly time to an np hard problem because you can effectively encode things like bin packing in this. I'm not going to uh go through the reduction um but maybe you can you can make it out from the example taken just from the paper. Uh you have the bins here of of five G's and then you have uh items of three and two and three and two separated by some A's. If there's a way to pack the bins tightly then uh you get here these nice stacked pairs but only between the elements that are from the same item. Uh if you have to branch out to other things, then it doesn't work and you can count um that you you only get the full number of stacked pairs here if you can fit the items in the bins without slack. And so you can encode bin packing. Uh hence the problem is is in general hard.

20:25 Um you can even uh look a bit closer. The paper does a bit more than than that. Uh but I'll leave it with this general message. We've now found a more reasonable formulization of the problem and ran into the complexity at wall.