Video 8-5: Grammar based secondary structure prediction

0:04 The chemistry based approaches at some point hit a a wall in that you you can't get much further with refining the energy models it seems and also the algorithms uh would get expensive if you were to include more of these inner loops. Uh so people instead tried to look towards u more learning approaches. Um, and so the the key challenge is to have enough data to do that. And unlike for proteins, it seems there's not enough reliable uh RNA structure data to just apply some blackbox learning uh machinery. Um this seems for for alpha fold there was I think uh several hundreds of thousands of protein structures are known all like a laboriously produced by some PhD students that seem to have been enough to train a system for RNA that's not not yet the case uh what you can do is still a machine learning driven approach but by g encoding in a sense more domain knowledge in the models you can reduce the number of parameters uh to a point where the available data is enough to at least in that model get get a a good fit. Um I think the apart from the machine learning side which I'm not going to go into in full detail there's a few cute algorithms and connections to formal languages that are are fun to explore.

1:36 Uh and that comes for uh essentially there the the model that gives you this this combination of a learned approach and encoding some domain knowledge.

1:53 And what we'll use for that are contextf free grammarss and then probabilistic contextf free grammarss. So let's just briefly remember what context free grammarss are. This is uh stuff you would usually do in some theoretical computer science class without any uh application maybe apart from parsing computer programming languages. uh a context program grammar has these four components non- terminals terminals rules and a start symbol and here's here's an example that's a typical one that you would study there uh you can I should have done these in green the parentheses are part of the uh terminals so This uh this grammar if you use as start symbol e produces all correct arithmetic expressions where you have addition and multiplication and you can generate the two variables x and y fancy you can generate numbers um either a single zero or it's starting with some digit and then continuing with potentially more digits. So you can produce numbers. I don't know. Uh you could have something like this.

3:22 That would be one one valid uh string that you can generate from this grammar. Uh the way grammarss work is that you start how do you get to this? You start with um the start symbol. You pick one of the rules to replace a non- terminal by the right hand side of what you have here. So here we would pick this one. So you generate an do it a bit more stretched out.

3:59 So I've chosen this first rule and replaced the non- terminal by these uh elements on the right hand side. Now I have further non- terminals. So I have to continue replacing them again using some rules. Uh let's replace this one. And here we use the rule that replaces by i. And then this becomes 55. So I is replaced by c. I'm uh seriously running out of space. Uh let's cheat a little bit. Maybe I have to com compact it a bit. So it goes to Z. And then from C we go to a five and C prime and then the C prime goes to five. Then I've produced the 55 plus. So you can lead it read it left to right. And there's going to be another sub tree for this E that I don't have space for. Yeah, I know. Uh, luckily we're not in uh formal languages. So, yeah, I can just appeal to you already knowing this.

5:00 Uh, one way to draw how you derive things in in such a grammar is this parse tree where you have a sub tree for each non- terminal where you replace step by step using one rule the non- terminal by the right hand sides and keep going until you've only seen until you only have terminals. Uh another way to write it is using leftmost derbations where you have a string of terminals and non- terminals and in each step you replace the leftmost non- terminal by some right hand side.

5:36 The usual application people have in mind for this is programming languages and parsing. So uh apart from just checking whether you can generate a string, you can build this parse tree and then continue working on that for example to compile some higher level programming language into some assembly code. Here we're going to do something different. Um we're going to treat the grammar as a probabilistic model or a class of probabilistic models. You could you should think of this as a generalization of something like Mark of chains. So maybe as also should have gone on the slide.

6:27 A mark of chain is a finite automaton with probabilities between the states. And depending on the model, it might generate a string or if if you think about information theory, a mark of source might generate a string uh where the probability to emit a certain symbol depends on the state you're currently in. And whenever you've spat out a symbol, you may make a transition to a new state or there might be a self loop to stay where you are. Um, but essentially this is uh the equivalent of finite automata in regular languages. Whereas the probabilistic context free grammarss would be the equivalent of context free grammar or contextf free languages. So they're a bit more powerful. Every mark of chain is also um a probabilistic contextf free grammar. as a special case. Uh but they can you can do more expressive models with these uh contextf free models. Normally for now um all we do is assign to for each of these uh rules a certain probability.

7:34 I guess I was a bit sloppy here as well. I didn't explain what this vertical bar means. Um these are three rules for E, right? E to the first part. E can go to this multiplication part or E can go to I. These are three separate rules in a formal sense. Each of them gets a probability and I want them to sum to one for each non- terminal. So whenever I have a non- terminal say E, there's I can uh throw some some random process that determines me which right hand side I'm supposed to replace it by. And I do this for all the non- terminals. Um maybe for some okay here they're all uh at least two different options. Sometimes there's not even a choice then that's fine. Uh the important bit is that it's a probability distribution for the right hand sides given that you know the left hand side. Uh if you do that then the probability of a derivation or a parse tree is just the product of all the used probabilities of all the used rule probabilities.

8:41 So the you could say I'm starting with the start symbol uh that needs to be replaced by some right hand side. So I'm going to flip a coin that decides which right hand side to use. That's probably going to add more non- terminals. So again I'm going to flip a coin to replace say the leftmost of those and I've keep going until all non- terminals are gone and replaced by terminals unless I made a mistake and made it more likely to keep adding more non- terminals than terminating. In principle I can do this which might mean my model is is stupid and broken. Uh you can avoid this with training in in the right way though.