Video 8-6: Probabilistic context-free grammars

0:02 We briefly looked already at grammar-based approaches which are um certain probabilistic models for RNA secondary structures. Uh different from these ainio methods which just means out of nothing you're folding just from uh the struct the sequence and nothing else. We now try to do a bit of a learning approach. Um it seems to be that simple blackbox approaches don't work yet. There's despite that if you Google for it there's plenty of papers that claim oh this this or that deep learning approach work perfectly fine for RNA and I always found them in the details not yet so convincing or they actually do a lot of similar things and have an added last layer of of some u modern learning approach on top of that but don't just really uh don't just do endto-end learning so I don't know uh it seems this statement is still true. Uh if you restrict the model then you can get by with much less data. That's uh the idea and what models work well and what don't don't is something we'll have to come back to.

1:23 Okay. On to computer science and and theoretical computer science. We talked about this briefly last time. This was a recap of contextf free grammarss. So these are these structures with non- terminals and rules to replace them with and they're always of the sort that the left hand side is a single non- terminal hence the name contextf free. You don't need to know the context to know what to replace a non- terminal with with and you can use these essentially to build nested structures which is hopefully reminiscent of the definition of secondary structures with these pairs. two base pairs, right, to be allowed in the secondary structure have to be either contained with each other, so well nested, or disjoint, also well nested, but not overlapping. That's precisely what contextfree grammarss are good for. So, it seems like a natural match in that sense. The other typical example um for nested structures are arithmetic expressions. And here's one possible grammar to define those. Um here in in the strict sense everything has to be surrounded by parenthesis whenever you do an operation then there should be parenthesis around those. So there's no special rules needed to decide operator precedence and then you can uh generate expressions like this in a probabilistic grammar. On top of this, you also have probabilities on the rules, which means here we're just seeing this uh as a way to generate expressions. It's an a way to exhaustively generate all valid expressions and only those. But that's that's it. There's only a either in the language or not. Um that was the notation we use here. So this calligraphic L of G describes the set of all strings that can be derived in the grammar. Formally we write this like like this. um S is the start symbol that we have to start in this grammar with and then this double arrow means applying one rule which means replacing in this sentential form on the left applying um one of the rules by replacing a non- terminal by the right hand side and the star means do that any number of times until you arrive at some string only consisting of terminals that's why it's green no more non- terminals Then this is one word in the language of this grammar generated by this grammar.

4:02 That's all classic computer science uh or theoretical computer science formal languages. Um there's corresponding algorithms that I'll briefly come come to in a second. uh what changes now is that we have probabilities on top and for this to make sense uh I fix the left hand side and then for all possible right hand sides for example here for E an expression can be either an addition or a multiplication or it's um an identifier these are three different options and if I have an expression I need to know which of these three options to pick so the probabilities of these three rules ought to sum to And then same for every other non- terminal. That's that's what this um definition uh requires. And that in principle induces a probability distribution over strings. And I mentioned there's this theoretical concern that you could build a grammar that doesn't ever finish. with probability larger than zero, you keep going on adding more non- terminals than you consume. In that case, uh this the the probabilities of all the finite strings if you sum over them, it's it's a number less than one. Other than that, nothing really bad happens.

5:25 You probably don't want to use that grammar to generate random strings because it might never terminate. But okay, we're not going to do that much anyways. So far so good context free grammarss kind of how familiar are people with those?

5:49 Uh in the standard computer science curriculum they would be covered in and out but um may differ otherwise. um already said this. Pseudonaut free structures correspond nicely to this and we can indeed uh represent together the basis and the secondary structures if we blow up our terminal alphabet. So that's what we'll do in in the next few slides that our terminals are pairs of symbols. one of the four bases and one of the symbols encoding the secondary structure. Um, since it's a week ago, remember secondary structures we had the outer planer representation. If you pull the backbone straight like in this picture, same as uh last time, then we can represent instead of these arcs, we can represent the secondary structure as a a balanced parenthesis string where I have these dots sprinkled in for unpaired basis. And whenever I have some some uh pair that's forming forming an arc here, okay, if I could draw nicely, then you would see it. And then uh you have these two symbols that correspond to that. And you see that if this string is correctly parenthesized, every opening PN has a matching closing PN and that's uniquely identified.

7:21 And you could for example say you count how many are open and then when you close you go back down or you follow follow a stack or different different alternatives how to do that but you'll find that these two are matching parenthesis and so they represent this arc. Okay. It's a oneto one correspondence.

7:42 Uh and it turns out it's convenient to have one terminal representing the pair of sequence and and structure snippet bit. Uh I don't think there's a name for these secondary structure symbols. Uh maybe someone should invent a name. So what I mean by is a a symbol that could be either a dot or an opening or a closing parenthesis. Okay, hopefully this is conceptually easy. This is by the way uh this idea how to pres this this presentation of what's to follow is some something we came up with uh for a paper and I haven't seen in textbooks and so if you read up on secondary structure prediction with grammarss it will likely be formulated in slightly different terms. it's equivalent and I think this is so much easier to follow but okay maybe um you'll tell me at some other point some later point whether you agree with me on that let's see some example uh we need certain grammars so that the resulting RNA sum uh sequences or the RNAs that we can generate from those make sense in particular we always want these second components of the symbols to represent a correctly parenthesized string, right? In principle, so if I just say this is my alphabet, pick any symbols from that and build some string that might just be uh without any meaning or it wouldn't correspond to a valid pairing. You could have more opening parenthesis than closing and all other nonsense. Um you could also have things like open close directly after each other. We know from uh the last time this doesn't actually form a valid bond. You need a minimum distance between.

9:46 Indeed, I think we said three unpaired bases is the smallest we we can allow. So this shouldn't be allowed. If you carefully check this grammar, it doesn't actually allow this, but it allows shorter hairpin loops than this. You can make the grammar a bit bigger and a bit more precise to avoid that. Uh for this first small examples, uh I chose not to. Okay, first of all, here's um the probabilities in this table are completely fictitious. They're just made up to show an example and I don't think they make a ton of sense, but that's besides the point. There's two non- terminals in this grammar. Uh, effectively S, you can think of producing an arbitrary number of L's, right? S can go to LS, then you've you you keep your S, but you've spawned an L, or you can delete S. So, you keep making copies of S until you decide to kill it. And then L itself can be either an unpaired base all the four options or it could be a pair enclosing another entire structure.

11:02 Okay. And this S again is the original S which means a sequence of an arbitrary number of L's which again can be the same thing recursive uh definition right.

11:19 Uh so this this statement down here I guess uh I think valid only said if there is a pair formed induced by these opening and closing parenthesis then it has to be one of those six options for the basis. Uh but we also need this minimal distance for for hairpins to be valid and this grammar enforces that between two parenthesis. No, it doesn't enforce anything. I could delete S. This one doesn't doesn't do any good, right? So that's not not even that is correct.

12:16 Of course, you can think about how to change the grammar to enforce this and that's one reason why people uh work with these grammars that it often makes it easier to describe such constraints on the model. um this grammar is not super convenient for doing that but it is of course possible by introducing more non- terminals. So you could have um a variant of S that produces at least one L. So you have say T which can also produce a sequence of let me let me write it like this. You can also produce a sequence of L's, but a non-mpt sequence. And so by using inside here between the parenthesis the T and not the S, you would enforce that there's at least one L and L is either another pair or uh at least one non-ter one unpaired base. That would enforce that they have hairpins of at least one non- terminal. And you can tweak this further as maybe you can imagine.

13:27 So by adding more non- terminals you can model such constraints more accurately um without going completely crazy because you don't have to change all the algorithms for the prediction for each little change you make. All right so for now just take this as one possible grammar even if it's far from the most useful one um to illustrate how we use this for secondary structure prediction. Um and let's do uh a tiny example on the next slide. The the key idea for for structure prediction is as you see in these pairs there's the structure already prescribed. So that I can't directly use. Instead um we'll ignore the second of these pairs of ter of symbols and only focus on the upper part when we try to predict for a given sequence what the structure might be. So uh wherever we have some a we could either have the dot or it could be this open or close uh here.

14:44 And you're kind of getting several possible derivations that differ in this in this second component but have the same symbols in the first component of the terminals. And then we can pick the most likely of all of these. Uh some of these terms on the slides aren't so well defined yet. Uh we'll get there. Um first of all uh most likely parse tree the the probability of a parse tree is just the product of all the probabilities that are of all the rules that are used. the product of the probabilities of the rules that are used. Uh that comes later on the slides formally. Probably would have would have helped to put it here as well. Um let's do a very tiny example. Here's a minuscule RNA GAC. And let's pretend that also a hairpin of size one is possible. The whole point here is just to give you a small example that fits on the slide, not a biologically relevant one.

15:49 In particular, you can brute force the possible options that uh that you you may want to check. Um you could have everything unpaired. That's one option. You could have the outer two paired. And let's pretend the other two um I would probably want to uh include this T inside here. Otherwise, there's a few more options. I could also have the first two paired and then unpaired here. Uh, sorry, the other way around. Um, these are the other two options I have. Right. Uh, for those two, here's a specific derivation written out. Uh, the dot on top of the non- terminal tells you which one is replaced in the next step. and whatever is grayed out has not been produced in the current step. So for this one, we start with the start symbol. We use this first rule. So the number below the uh derives arrow is the probability that we do this step. Then we replace the L with um the unpaired G.

17:00 That's this one. And that's probability 1.1 0.1.5 and so on and so forth. Then L goes to LS. S goes to LS. This L also goes to unpaired. Then we have another S here that goes to LS. And then the L goes to the last one. And S is deleted with the second rule. If you multiply out the probability for doing this derivation, if you are just running this um starting from the start symbol randomly, the probability that you do this step is whatever that number is. fairly small number, but the absolute number is pretty meaningless. We should compare it with alternatives. And so here's the uh alternative that produces the outside pair. You get the pair here from the first L. There's an S inside. This S outside here will eventually just be deleted. But I wrote down the derivations as a leftmost derivation where in each step you take the leftmost non- terminal and replace it.

18:04 Okay. Then this S gets another L and that is replaced by the unpaired one and then we delete the two S's. And if you multiply out here, we would find that this has also a minuscule probability. But again, absolute numbers here are useless. It's more likely than this one by a factor two roughly. So this one would be the predicted structure. I should have added the other two options and checked that they are not more likely. Um the way this grammar is built uh yeah they're not valid pairs right GA and AC are not possible in this grammar. So there's two other possible secondary structures, but these are invalid in the current with with the primary sequence that um with a with the sequence I'm given, these wouldn't form valid pairs. [snorts] Okay, that's how the prediction works. And you see how it's um it's natural to say what your predicted predicted structure is by just reading off the second component of all the terminals. And imagine you were to kind of well I haven't told you the algorithm but suppose you were trying to implement this and now you're you're checking what is the next rule that you could use. If whenever you check a terminal against the string the position you just compare the the first part of this pair and ignore the second that's easy to do okay may maybe I can comment more on this when we get to the actual algorithm that that's the rough idea um we have a grammar that describes pairs of sequence and structure and we can use that for predicting structures given only the sequence by conceptually going through all possible derivations checking that they match in the first parts and computing their probabilities and then predict the most likely.

20:16 Okay, of course you don't want to explicitly go through all possible derivations. There are clearly exponentially many in general. So we need a more systematic approach but that's where the formal language theory comes in. Uh before before we go there let me um give this more schematic overview of how we use grammarss here. Um and this is more generic but uh here that's that's how we use it. So we uh as as often in machine learning approaches split our data into some training data set and then the data where we want to predict on and we need in this case training data where we know the true the ground truth the existing structures and there's some data sets where these structures have been experimentally confirmed and you can use this uh as ground truth training they're just not huge okay we also need a grammar which is this this uh template of what rules exist and this is basically uh up to us to come up with. The uh approach here assumes that the grammar is fixed.

21:32 From the training data we can take the grammar and parse the structure which means determine what rules are used in this grammar to produce this pair of sequence and structure. Hopefully that is relatively um unique because you're with a known structure there's no particularly good reason to have several derivations in a grammar. Now that said um if you just design a grammar not carefully you may have several derivations for the same string. It's totally possible but you can avoid it by being a bit more careful. So you you compute what rules are used in your training data set and then you give the rules probabilities but just counting how often they were used and that um gives you the the rule probabilities for this this uh stochastic model.

22:30 The grammar itself the way I describe it here is just the structure without any uh rule probabilities. These are determined from the training data.

22:38 If once you've done this, you can take this uh probabilistic model with new data where you only have the sequence and again determine with an algorithm yet to be discussed how uh what's the most likely derivation that matches this first part and that most likely derivation second part is the secondary structure you can predict. Okay. Uh we'll see that the two critical parts um the parsing here and this most likely parse tree there can actually be done with the same kind of algorithm with a um slightly different handling of the terminals.