Video 8-6: RNA Grammar

0:02 Let's come back from the lovely excursion to formal languages to applying RNA uh to to applying grammarss to RNA structure prediction. Um, it turns out that this lovely Schomsky normal form that we've used in these dynamic programming algorithms is really rather inconvenient for RNA for the simple or maybe stupid reason that all we care about all the time is to produce these well parenthesized expressions. And so it would be very convenient to express that in a single rule we produce an opening and a closing parenthesis so that we can locally make sure that everything is correctly parenthesized. That's just makes it much easier to reason about these grammarss. But Shamsky normal form forbids this. If you think about the dynamic programming algorithms, where did we use that the rules the right hand sides don't contain extra terminals?

0:59 We don't actually use that. It's not too hard if you um imagine if you look at this this recursive part. So this is only for tiny substructures. That's a special case anyways the base case. This is the general case where uh you ask yourself is there a way to split up my range from I to J at some position K so that I can produce the left and the second left part and the right part separately. Now I could easily say I'm leaving out one or two positions here at the beginning or end of these ranges and force there to be a specific character of the string. that's not it's not making the algorithm much more complicated and so we don't have to slavishly follow this shsky normal form really the same dynamic programming algorithm also works um if you allow a few extra terminals on the right hand side the other uh the other power point is a bit more thorny in that uh I'll I'll show you some examples later for what these RNA grammarss that work a bit better for prediction than the first I've had on the slides, what they look like. And you can often even read them in the sense, oh, this always produces a multiloop in the structure or this always produces a bulge or this produces stems. Um, and often times you have some non- terminal that stands for the disjoint union of several of such groups. And then it's very convenient to have chain rules to say here's the superass and it could go to one of those three options.

2:46 But Chsky normal form disallows these chain rules. Right? I can't have a rule A goes to B. And there's a good reason for disallowing those because these chain rules again what I mean is A to B these kind of rules those are potentially dangerous because you could have a cycle and then all the whole uh well then things become much more complicated. Let's let's say it this way. You can still define things to make sense, but it could suddenly now be that the vurby value for some perverted reasons uh wants to include cycles. I guess not really, but the sum the the uh if you want the other uh metric compute the total probability of a string, you would have to sum over this infinite class of derivations. This is in in principle solved and possible but it makes everything more complicated and we don't really uh want any cyclic derivations anyways for RNA they would never be productive or useful.

3:53 So we want to not have those but the chain rules are convenient to write down grammarss. So what can we do? We want chain rules but we don't want cycles. Then we have to make things as cyclic, right? So, uh, a cycle from A to blah blah blah and then back to A. This is bad. We don't want that. Some chain rules sprinkled in in the middle are okay.

4:27 So, what we'll do is we'll insist on some total order. I'll comment on the other forms uh of rules in a second. uh we allow chain rules but we only allow them if they go to a smaller index and that way we can for sure uh exclude cycles.

4:47 Um a few other things uh just for the notation um well we give non- terminals numbers is basically just for this last rule. I think that the rest would work either way. The other rules are similar to Shamsky normal form. The first two are exactly what Chsky normal form also allows. And then there's one more extra form that I'm allowed to use where I produce a pair and then some other non-terminal in between. This is formally superficially against Shsky normal form wouldn't be allowed but as I maybe hinted at already, you can just adjust the ranges in the dynamic programming and it doesn't actually cause any issues.

5:31 Um so this is uh something we suggested as a normal form. I don't know if uh I'm I'm not aware of grammars that are useful for RNA structure prediction that wouldn't be expressible in this form with a little bit of tweaking. So my my reading is it works well. Hasn't been contested yet. We can compute vurby values for grammarss in this form in roughly the same way. Uh again we can have the base case that I'm producing a single terminal from this non- terminal a that works only if I have such a rule that's these type two rules these guys. Uh you know what would be useful is having the meaning of these on that slide as well.

6:33 I annotated it with a type of rules but not the meaning of what that rule type looks like. Uh for for the general case I'm generating a larger string. Um it could come from one of those three types of rules. For the first type, this is literally the same as the Shsky normal form. So that's exactly the same as before. And for the other two, I have to slightly tweak what I'm doing. In each case, I'm taking the maximum of all options that fall in this category. I always have the probability to uh use that rule that I'm choosing as the first thing and then I have a recursive term for the rest.

7:16 For the type four rules, it's the easiest. I'm using I and J the same way as here because it's a chain rule. I haven't actually uh produced anything. But I've used one rule. So I'm adding this this factor in. And here automatically because these rules A to B, they only exist if J is an earlier index. You see how the subpros for the recursive for the dynamic programming become ordered. If you iterate over the index of the non- terminals in the right order, you always only access sub problems you have computed already.

7:56 Uh for this for this rule, um it's conceptually easier. It just looks a bit more annoying because the rule now consists of terminal B terminal and so you split off one position on either side.

8:10 It's kind of obvious how to generalize once you've seen it. Okay. So we can compute vurby values. That means we can take um a given sequence. And here whenever we say that we need such a rule here it just says wi which is a terminal in the string that we're parsing. And it's it's up to us to decide what that means. We could either take the pair of terminals and compare them both or we could just focus on the base and ignore the second part. Then we get what we've done before. We can use rules whenever the first part of the terminal symbol matches. So we get the most likely derivation for all of them that give the right base sequence and we get the secondary structure in the produced uh second part of the terminals.

9:13 Um, okay. Let's go there first. Fine. Uh, you've seen all the algorithms so far. Even though you can tweak a bit what kind of grammarss they apply to, you you can't really get away from the cubic running time. That's not completely useless. You can apply this for RNAs of say size a thousand. But at some point it becomes really expensive. You also have quadratic space which is hurting at some point as well. Maybe we can do better than that. And it turns out there are some steps in this direction uh that are theoretically interesting. Um one option is to use a connection to matrix multiplication. in that if you especially look at the classic CYK algorithm, it has a bit of a a kind of matrix multiplication flavor um it's even easier to see for the Nusenoff algorithm which was just counting maximizing the number of base pairs. So uh no grammarss involved there even um in particular here this I mean there's these other cases where you have an unpaired base these are uh very cheap because there's no further maximization.

10:34 So if you only had these parts the total time would already be quadratic. So in a way you can think about premputing those first and what's left is this last part. And look at what you what you're doing here. you take the maximum over di plus dkj with the uh I'm lying away the plus plus one here that feels a bit like a weird form of matrix multiplication where the multiplication is replaced by a plus and the addition is replaced by maximum. So it's uh Other than that, it looks a bit like matrix multiplication, right? So maybe there's something there.

11:35 Before we even go in there, we can apply exhaustive tabulation in similar ways as we've discussed for alignment problems. So yes, you can shave off some log factors with that. People have explored this. I think log squared is is the best that's known is is cool. So you get I think the the best I've seen was n cubed over log squared.

12:01 Uh don't quote me on this. The other point is this is cool but not so exciting. uh it doesn't reduce the the complexity by all that much. Uh another promising route that has been explored is um based on valian algorithm which is a clever um clever insight that for standard parsing contextf free language parsing where you uh just ask is a word in the language or not. This in general you can express via boolean matrix multiplication and matrix multiplication that the end result should be boolean. You can ignore you can just use any matrix multiplication algorithm and that's an interesting problem with a long story of its own. Um but you can apply any of these algorithms and there we know it even has this a coined term this omega the exponent of matrix multiplication is uh whatever it is 2.3 something right uh what's the current asmtoically best uh that's known and well you can you can look up the numbers they keep going down a little bit once over once in a while [snorts] These are theoretical results. The algorithms are are slower than simpler methods for most input sizes that are ever relevant. Uh Strassen's algorithm is somewhere in between 2.8. Still that has some uh some uh hope to be practically efficient.

13:39 Um so in principle context free parsing doesn't need to be cubic time. you can in fair in fairly general sense replace it with matrix multiplication. Uh but it seems um if you want to apply this to RNA folding there's some conditions to the precise model of what you're doing. So it doesn't completely follow for all variants that we looked at. And the other um option is using this this uh connection I mentioned here that essentially you're already doing something like matrix multiplication but not with the usual arithmetic operations but rather this max plus or min plus is the same if you just flip signs. Uh and that is interesting in its own right again because it's effectively equivalent to all pairs shortest paths in graphs. Now you'd think uh just taking min and plus instead of the normal operations that shouldn't make a big difference but it does uh these kind of matrix multiplication algorithms with this better running time they don't work for this min plus and it's not known how to do this in general in fact it's very very unlikely that we can even do it in general this is based on some fine grain complexity so the assumptions are maybe more questionable who knows um but is at least making progress on this also simultaneously makes progress on other interesting problems.

15:13 But for special cases of this min plus matrix multiplication, some better results are known and these again apply to some versions of RNA folding. So there's some theory work that goes in this direction and uh you can slightly shave off of this exponent. I don't think there's anything much much more scalable than that node. There's uristics known uh but nothing that gives you the optimal structure in some well- definfined model.

15:52 That leaves us with for the grammar approach the decision what grammar to use. And that's uh something I've I've avoided saying saying much so far. Um, and the reason is that we don't really know. It seems at this point more art than science. Like many things in machine learning, you can try out a lot of different options and you can quantify how well they work. But it depends on anything and everything from the training and testing data set uh to uh the the metric the precise metric how you evaluate. Uh for example here suppose you have some prediction algorithm that takes your your structures you have a a data set where you know the ground truth but you're evaluating your algorithm on it. So you have real structures and you have predicted structures. So what are you going to do with them? Uh how do you evaluate the the algorithm? Probably they're not going to be identical. So you need some way to determine how close two secondary structures are.

16:57 Uh so one one problem there is this evaluation. And the state-of-the-art seems to be you count the number of pairs that are identical and you take the ratios in the typical sense of precision and recall. How many pairs in the correct structure have you found and uh how many are correct? Uh how many have you missed? Um is maybe the best that we have but it's a very crude metric. So that's uh also something if you if you play with the metric then um different grammarss do differently well. Um already a while ago uh there was a paper that took various human expert design grammarss and said let's uh let's ask the experts in the field to produce grammarss that they think are working well uh without asking them to justify why just uh gut feelings basically and compare them in some well-designed experiment and even though it's it's over 20 years old I think the the results are still meaningful. There's there's many more RNA known now or there's bigger data sets known um but I think the results are still representative and this was one of the top performing grammarss that they had there. You should read this bottom up.

18:40 So this start symbol is S. S can be a sequence of T's obviously. Then T is an option. It's either a U or a B. The U is obviously just a unpaired base. I could have maybe just inlined that. And a B could be well some pair with some stuff inside. And the stuff inside could be well another pair or another sequence of T's.

19:08 So you see there's certain structure to the grammar. It distinguishes certain cases and uh collapses others. for example, that you always have the choice indep independently of what t is translated to and this this seems to work well. Other grammarss that superficially sound equally sensible didn't do so well. So I think uh that's the part about art and science here. I wanted to at least show one concrete grammar on the slides though that seems to be uh if nothing else comes to mind a good starting point.

19:57 Let me branch a little bit into some some research that we've done and that's motivated from precisely this last point. Um first of all fairly general in machine learning even there's some some theory about it but let's uh let's leave it vague here. If you want to predict something then that often can be expressed as some understanding of the structure of things and then generalizing it to new instances. I guess at that level of abstraction you can't say anything that's wrong. Uh so I don't know. um forget it. Maybe uh in this concrete example the the concrete thing that we can do is we can use these RNA grammarss to compress a sequence structure pair or RNAs where we know both. How do we do this? Basically the grammar tells you a leftmost derivation that constructs exactly this sequence structure pair and you can say I'm going to take the rules as my representation of that RNA and maybe the rules can be com compressed more than the original structure because the grammar gives us some hints of what's possible next in particular a compression of the sequence of rules I I just said here we can use we can compress it using arithmetic coding. Um the point is that at each point you know what non- terminal is replaced next.

21:28 So at every point the next rule is only one of the right hand sides for the current non- terminal that we're replacing. Initially that's the start symbol and inductively it's the leftmost non- terminal in the current form. So I already have some guidance from the grammar about the options of what could become what be could be the next choice to make.

21:53 So there's on one side the hope that this could be um an efficient compression of RNA but maybe we can also use the compression ratio of some grammar on on a specific data set as a proxy for how well it would do with prediction. And uh this is in in a way a more information theoretically principled way to compare models as opposed to doing this counting the number of pairs they happen to get right where you're doing some very indirect job. And even if if two structures are just shifted by one position, maybe they're still, you know, similar in in some sense. Um but this counting pairs would disregard that similarity entirely.

22:43 That's what we looked at. So maybe I can show you just uh very briefly some impressions from there. Uh let's start first here. That's that's the 2004 paper comparing different grammarss for how well they predict. And they have a lot of text explaining the model and how they parse. That's um stuff you already know. uh wanted to show the grammarss that they play with. So this is uh this a sa that's supposed to mean open and close. The two a's are the parenthesis and the single a's are unpaired. >> Such a nice way to write parenthes. >> It's such a nice way to write this. Uh don't ask me why they chose this. Why not? Um I mean we should ask uh the authors in this case. Uh for some reason >> 2004 not retired. >> No no no. Uh at least I think Sean or Eddie is still running a lab in Cambridge. >> I would assume maybe not anymore.

23:54 >> What's that? >> I would assume they don't remember this way. >> Maybe there's a good reason. Maybe it was just the most compact way they could think of. probably >> as I said this way of representing the terminals as pairs that's something I made up because I was frustrated with the notation that other people used that's part of the frustration uh fine um >> as you probably don't spot right away both of these grammarss are highly ambiguous in the sense that even for the same sequence and structure they have several parse trees so these these should come out as really bad grammarss because they're nonsensical in some way. They included them anyways. And the funny thing is the the second one doesn't even do so badly. Uh and there's there's a few other ones. Um G6 is essentially the one that I had on the slides, but I had to massage it a bit to for fall in our normal form. So it looks a bit more compact the way it's written here, but it's essentially the same grammar.

24:58 Uh okay. And there's two more which are a bit bigger. This may be a fun thing to mention. They call them stacking grammarss because here uh let's see where can you see this. The notion here notation here is supposed to mean that you pick some a and a head. So an opening and enclosing parenthesis. But remember in in sequence language these are two bases that are uh that are paired and then the non- terminal inside remembers the two bases that you used. And this is chemically this makes a ton of sense because the stabilizing contribution of nested pairs depends on what kind of uh neighbors you had. And so here they use a blown up number of non- terminals. It's basically one non- terminal for every uh enclosing pair to be able to distinguish in the parameters between these different neighbors. And you you'll see that these uh stacking grammarss G7, G8, and also G2, they tend to do a bit better.

26:11 And they have one one lovely table at the end. Okay, that's the size of the grammarss blah blah blah. So you see for these stacking grammarss you get a lot more I think that's the number of rules roughly I don't know what the parenthesis mean uh three parameters okay the rules of one non- terminal after sum to one so you jump from a few dozen parameters or probabilities to u several hundred if you use these stacking uh grammarss And this is the full uh the final results grammar uh final results table where uh sensitivity is um how many base pairs you correctly predicted and ppb should be how many of your predicted pairs were true ones. So in a way you want you want the mean of these two numbers. Um so they unfortunately didn't compute that but you can see that G6 does re reasonably well. Both numbers are relatively high and the stacking grammarss are further down here. Okay. So uh the best performing seems for me G6S which is a stacking version of G6. Okay.

27:43 And they compared it with some some other concrete tools. Okay. So that that was uh that was what comes out if you take these very crude metrics of how many pairs did they get right. Um then we set out to say can we instead take these grammarss use a data set with known structures and see how small the compressed size becomes do that for all the grammarss and compare do the grammarss that compress well also predict well or is this kind of a different problem in principle it there's no it wouldn't need to go hand in hand because prediction uh doesn't care about overfitting. Uh sorry, compression doesn't care about overfitting. Prediction does. In prediction, you try to generalize from known structures to new ones. In compression, you know everything and all you want to do is uh reuse some or find find reused structures, something of that sort. Um okay, much further down. So first thing is we took these grammarss from the previous paper that you've just seen uh plus some others that I can comment on uh and compare it on on this on their data set in a way. How small are the compressed sizes of the grammarss? And the way you should read this here, this is averaged over the entire data set, but then divided by the number of bases.

29:28 So the numbers here are the number of bits you spend for a single base. And so a reasonable number uh to hope for could potentially be two bits per base because we have four different bases. So two bits are enough to say which out of the four bases there are. It's known that RNA sequences, same for DNA, by the way, um if you just look at how often each nucleotide occurs, they're roughly equally frequent. Which means if you just compress uh using say a Huffman code of the four different symbols, you're not going to get much better than two bits per base because they're not very compressible in this sense. However, here that's the sequence plus the structure. Okay. Now, if the hypothesis is true that essentially the sequence entirely determines the structure, storing them together should take not much more space than just storing the sequence. That's uh that's the theory. Uh that would be the case. If you get down to two bits per base, it would mean that you pay nothing extra for the structure.

30:41 the sequence gives you the two bits per base and you don't need any extra. Uh that's not quite true as you can see but it's also not completely untrue. Uh you see that these grammarss especially this this one here which is a huge grammar that tries to distinguish all possible shapes that are distinguished in this minimum free energy model. the Turner suker energy model. You get reasonably close um to two bits per base, although not quite.

31:15 Uh let me show you this this big grammar just to make the point for what a big grammar looks like. Has all these rules that distinguish a gazillion different cases. Um it seems to help at least a tiny bit, right? Okay. Okay, but the interesting plot I have skipped so far and that's this one where on the x-axis you have the same data as I just showed uh kind of the mean is is the x direction and there's some error bars and then on the on the y direction you have the geometric mean of these two columns in the in the in the table from the paper before. So take these two take the geometric mean which is a reasonable way to combine them here. Um and then you get the y uh value. So here higher is better because uh that's quality of prediction whereas for compression lower is better. So the top left corner is where you want to be right.

32:26 And you see that these these three grammarss G6, G7, G8, they all roughly equal. And there's error bars here which mean okay even that they're not precisely equal. Maybe you shouldn't over interpret. But the other interesting feature of this plot is is a relatively clear correlation almost linear even which means if a grammar does well for the compression it tends to also do well for the prediction. So there's some hope that if you take new grammarss and you do this very simple experiment, take a known data set and compress it, then the compressed size maybe is a good surrogate for doing this more more expensive uh and more fiddly uh prediction study where you always have to decide how do you compare the true and the predicted structure in detail.

33:27 And then we had a follow-up paper that uses this to try to find better grammarss than these human created ones. And in the end, cutting the story short now because we're out of time, uh, we found a grammar that indeed does slightly better than all the human grammars. And I'm zooming in because I remember that it was in the in the decimal digits. So the best the best compression it's a different data set that's why the numbers are slightly different. Uh the best of these grammarss here I guess is this one.

34:07 And this one is ever so slightly better. Uh, and this is a grammar that we just found by randomly trying random grammarss, checking how well they compress and keep going. The numbers talk about the size of the grammar. It's just I'm just saying at this point this was without any clever algorithms. Um, it was just random guessing and keep that running on the server for a few months. uh it went through an insane amount of grammarss and it found one that indeed at least outperforms these human expert grammarss even though only by a tiny bit. So I feel there's um there's some truth in in the whole story.