Video 2-5: Waiting for words

0:02 In this section, we're looking at the gene detection motivation and now turn it into the computer science problem of computing how uh much signal we get from specific uh open reading frames in particular. Um and one one key question for this is how big genes really are. um if they were all very very short or if they were all at least in a specific range, we would be very much out of luck. It turns out that they're usually much longer than is needed for this. uh this the specific gene in the genome browser that I've I've shown you briefly and I'll go there in a second just to show it again uh is this MC1R gene uh which is one of the key genes uh for red hair coding for the specific um uh type of uh of of red hair often combined with bright uh skin etc. So it's is a one of the genes where you can directly see if a person carries it or not. So it's a bit of a um a rare uh event in or a rarity in in humans that the single gene is so visible.

1:15 Um therefore it's there's even a magazine called MC1R magazine. Um maybe with specific I don't know what articles they have. There was one about sunscreen. Um let me briefly show the genome browser again. Um that's this this website where you can zoom in on any part of the human reference genome and they have essentially collected a lot of information that is is known or suspected about specific regions in the genome. And here's the MC1R gene specifically. It starts at precisely this point with the start code as you would expect. Uh and then it keeps going for a very long time. Here's the uh uh the sequence in the DNA and here's the translation to amino acids three at a time exactly as in the uh in the the video we've seen before. Uh and you already see um you can keep going for a good bit. Um and I'll zoom out a bit here to make it more visible.

2:23 Uh so you can already no longer see the DNA sequence. you can still read the amino acid sequence. If you go further out then even that is is substracted into some uh just some some bar and okay maybe we'll uh we'll have to leave it with that.

2:59 I don't want to keep uh waiting for the website for the rest of our uh lecture. So there is an end to this to this gene. That's as much as I will promise.

3:15 Okay. And if you go to the end, there is a stop code on. Um maybe I'll leave it without and you can you can check for yourself if you want. Uh a few basic facts just about the human genome. Only roughly 10% of the entire three billion bases are known genes. I guess we should say um is around I didn't write down the number uh oh gosh it's it's around 20,000 genes roughly. uh there was a suspicion at the beginning of the human genome project that it would be uh five times as much and people were a bit astonished at the time that the number of genes seems to be much lower. Um anyways uh what's the length of the genes that will become important for us in a second. Uh there are some genes that are very very short just 62 uh 63 bases. This BP is the usual unit that people give. It's just letters. Uh they people write BP because it's base pairs. And you'll remember that DNA always has the double strand.

4:21 Uh this also means by the way that typically genes can be on either strand. The translation doesn't doesn't matter. So you could either have the gene in the forward direction the way we've seen it in the genome browser or it could be the reverse complement where every letter is replaced with its uh partner and it's reversed. So whenever you do something with genomic sequences, you have to keep that in mind that there might be both options and either one would work. So this one's a um an exception. The otherwise shortest protein coding genes were uh more on the order of a few hundred bases. Uh the longest one that was is known as 2 million bases. That would be an enormous protein. But it turns out almost all of this is actually cut out during translation. So there's these uh these sequences that are called introns. They're part of the gene in the DNA sequence, but they will never end up in the protein because before the messenger RNA leaves the nucleus, there's loops of this cut out and connected again. The video just showed a segment of this RNA vanishing.

5:32 The way it's really uh happening seems to be there's certain parts brought together then there's a loop formed. The loop is cut out and recycled and the rest is glued together. And in this case for this enormous gene 99% of this long sequence is is cut out again. Why things are done this way there's uh is not 100% clear. It might just be a way to slow down the translation of this gene because this guy uh is so long it's um taking roughly six hours to produce one copy just because the copying process takes a certain amount of time. I think I read um maybe 2,000 base pairs per minute is the translation speed. It's not super fast, but it's happening at massive parallel scale, right? all the time 24/7 and in all the cells.

6:27 Okay. So a typical length of a protein coding gene is of the order of a few thousand base pairs. That's what from this long story that's what you should keep in mind. The rest ignore. Okay. A few thousand base pairs. Is that good or bad news? Can we reliably distinguish these from just having some some random uh open reading frames? Um I want to ask you this question, but let me define the model first. Um this is the null model. Suppose there was uh no gene there. We we pretend we found some open reading frame. Now we want to know is this an actual gene or am I just seeing a statistical fluke? is this uh by random chance there's an start and a stop code on and the whole thing in between means exactly nothing. How can I distinguish these? Um we'll analyze the probability that this this gene forms in a random sequence that's completely uh without any meaning. So we pick a a long DNA sequence. Every character is uniformly at random independently of all the others chosen from the four options.

7:46 And then the question is um if I uh have some occurrence of the start code on and then the next occurrence of the stop codon, how much is in between? That would be an open reading frame. And um that's what I'm comparing with the one I find in the gene the genomic sequence.

8:03 And so let's let's play this game. I mean I haven't told you. So um there's no right or wrong answers at this point. What what do you think? Just uh intuitively uh type it on the uh on slido if you can. Then uh we can record it also for the um uh people in the live stream.

8:42 And here I'm uh I mean 20,000 uh that was in the the actual human genome and we want to compare this with a random DNA. Okay. So you're just generating you're uh rolling dice instead of using an actual genome. Probably what comes out is not a um it's not capable of living.

9:08 It's a probabilities question, not a biology question. Well, since this is not a a knowledge question, let me uh Okay, maybe I don't want to influence if if other people are are still thinking. Maybe it's it's best to get unfiltered what you think individually and then we'll do the comparison afterwards and I get to enjoy to see already what you voted. Anyone [laughter] still thinking or still typing? So, let me show uh what we've got so far. Um 20,000 and in the order of millions.

10:23 let's do a a quick back of the envelope calculation first. And um I'm always going to already going to tell you that this is not an accurate way to calculate things and you can you can try to think about why and uh then we'll do the proper solution. Uh but I think this is this is insightful to do.

10:53 I guess I should also draw an envelope, right? But it's the back of the It's the back of the envelope, so you can't really see the front.

11:02 Uh, okay. I'm I'm not an artist. Um, so we have a sequence of DNA, uh, which is not dotted. Um, and suppose there's the start code on, I'm really embarrassing myself. Um, I don't want to mess it up. What's the ATG? And let's pick T aaa. I can remember that one.

11:40 That's what this thing has to look like. And in between no stop codeons, right, in all of this range, that's that's the the important bit. Now the start one we're kind of we're only start looking once this has happened. So I'm I'm assuming we're sitting right here. And now the question is uh when do I see the next stop code on? Now let's do something simple. What's the probability of any specific threelet sequence being a stop code on? So what's the probability that if you take three random letters it's uh one of the stop codeons T AA TGA and T I'm I'm really not T A TGA both goody say it again >> that's Right. This is three out of the 64 uh options of of picking uh three letters in this in this model. Is that big or small? Well, who knows? I mean, it's a it's a certain number. It's it's roughly one over 32 or so. A bit more, right? Uh that would be two. Maybe it's 1 over 20. So, I don't know. Very very roughly something like this. What does that mean? Well, it means whenever you move here, uh, you have a one in 20ish chance that the next thing stops the sequence.

13:22 So, in expectation, maybe we should expect 20 or so of these codeons and maybe then uh roughly uh 60 as as a ballpark for the length until we see another stop code on. So um maybe around 20 codons.

14:01 Another way to say it is if you you look at uh the codons out of 64 codons three are stop. So that's the same thing again. Um again um this is incorrect in a specific way but is also the order of magnitude is not wrong if you compare that to what we've had 64 base pairs for this smallest degenerate one but most uh genes of the order of a few thousand That's great because that means if you find this very long open reading frame, you can be quite sure intuitively or qualitatively we're quite sure it's an actual gene because if the whole thing was random, it's very unlikely to see such a long reading frame without a stop code on all the way.

15:02 Now let's let's get a bit more precise um because uh there's some some cute math that you can apply to this and uh it's uh um with these kind of probabilities you can in hindsight I can say what we got with the back of the envelope method is the right ballpark. Uh but you don't always know up front.

15:28 So what we want to answer this question a bit more accurately is uh the expected length say of a word that we assume we've just seen the start code on. So we're starting right after this. Now we count how many letters do we see until we for the first time see one of the stop codons. I apologize I've used the U here again because we're in RNA world. uh is a it's the same, right? Just uh uh replace t and u uh whenever you see them. Uh maybe we should decide for one letter and just ignore it. So we've just seen the start code on. Now we keep reading letters until for the very first time we see one of the stop codons and then we stop. That's a a language in the formal language sense of all strings that end with a stop codon and do not contain a stop codon anywhere before that.

16:21 Now it turns out you can write this question as a regular expression or you can uh draw a a DFA a deterministic finite automaton that accepts this language. In this case it's it's relatively straightforward. So I've just done it done the example and we in a way will revisit this question and how to systematically compute this in general um in one of the upcoming units. uh the states in this DFA will just encode the the last letters we've seen and more precisely the longest prefix of any of the start codeons that we've seen so far. So we start with having not seen anything the empty string if we see a U which is the start the first symbol of all the three start codeons then we make progress and we remember we've seen a U now along the bold lines we make progress in the same way we can continue reading one of the stop codeons for example UG brings us here then these accepting states mean we we stop uh but if I'm Say in this state I've seen a UG.

17:34 If now an A comes, I know what to do. But if I if I see a U instead, uh I can't continue. I have to give up this this UG prefix is not going to continue. But I have to jump back to this state because the U I'm reading now might be the beginning of a new occurrence of a potential occurrence. Was there a question? >> Sequence. Does it matter? Like do we get like U or because A so should not get A first and then U and then G. >> Uh we need to see them in the right order. That's right. >> UG is also the final state which is affecting but we want AUG. >> Uh no AUG is the start code on and this one is not part of the automaton. That's why um um it's it's same as in this picture. I'm assuming we've just seen the start code on and now we wait for one of the stop codons which are these three. Okay, it's just by chance that one is the reverse of the other.

18:40 So what what confused you I think is that a UG is uh the start code on um it's not exactly this reverse right u the palendrome but I guess there's so few letters that's not so surprising so aug doesn't occur in the automaton because we assume we start the game here once we've seen the start code on interested in the conditional. So the the conditional number of characters you still have to read after seeing the start code on before you see the first stop code on and that's the language that this automaton um accepts. It can be described this way. You can of course from the automaton read off uh other descriptions of the language but it turns out the automaton is the most uh natural one. And again just to to reiterate um is there any other interesting uh in this case it's it's relatively easy there's only this this one case there's sometimes a state like this ug state where if you read a u now so here this state means we've seen some string and it ended with ug and now there's a new letter coming maybe a u what's the best guess I what's the longest um prefix of any and longest beginning of any stop code on that I could have seen at this point and that's only U. U might be the first letter of any of these. The UG G are kind of not not going to lead anywhere. So I'm forgetting them. Is that is the automaton kind of clear? Um to make the connection for people, this is essentially uh the AO chorus automaton or string matching automaton for single string.

20:45 I'll explain these in more detail in a later section in the kind of systematic way. Here for these specific strings, it's kind of easy enough that we we just uh manually figure out what this automaton should look like. Okay. Um from this we can analyze how long the expected open reading frame in the random string would be precisely.

21:28 backward >> this one. CG >> C and G >> C and G should be inseparate to the >> Yeah. So what I mean by this this kind of a a bit of a sloppy shorthand notation I guess uh it means any of these letters the automaton always reads a single letter and here C and G do the same thing. They both go back to the start state same as here uh anything that's not a U keeps keeps you in this uh initial state. Yeah but that's important. That's a good point. Okay. So, what we what we'll do um is analyze the expected number of characters It's one of these cases where it's easier to solve a more general problem. We're actually just interested in the number of steps it takes from the start state to any of these accepting ones. Uh we'll do it for all the states because then you can uh relate them to each other and calculate it for all that turns you uh in particular it returns the answer that we want for for the state qpsilon.

23:06 So I'm just going to yeah here maybe I should have called them Q subscript but that that's less readable. Uh I want to dist I want to make clear here that I'm talking about this state and not just the string epsilon. Uh we want this for qppsilon but we'll do it for all of them. Uh for some of them that's really easy. uh and let's call this number um let's call it t and then this this substring x that's the expected number of characters from the state where we've have this label x to some accepting state. I'm just going to be a bit uh sloppy with the notation, but I could have listed all these three. Uh so we'll need the automaton to keep things in mind.

24:07 Okay, my laptop claims it's lost connectivity. That's not good for the live stream, but we going to ignore that now. So this is the the TX. That's what we're going to write down. There's some of the states where this is super easy. Namely, all of the stop codeons.

24:29 I'm already at the state. So there's nothing more to expect, right? I'm it's just zero. I'm done there. for all the other states. Uh we don't know exactly because it's random. The next letter is random. But we're talking about the expected value. So we can uh we can still say something. For example, for UA, there's uh a one in4 chance to go to T UAA and there's another one in four chance to go to T U A. Now, of course, I could have shortcuted this because these are contributing zero. Um, but uh there's there's one thing missing. I'll I'll come to that in a second. Then there's also these two outgoing edges for u and c. So with probability 14, I'm going back to tu. And with probability one quarter, I'm going back to tepsilon. But I shouldn't forget that I've taken a step. So I also need to add plus one. In all of the cases, I'm making this one character that I'm reading now.

25:44 Okay? And maybe it's kind of obvious already from this example. You can do this for all the states. For all the states, you can sum over the different outgoing steps. And you're going to um arrive at some system of equations.

26:03 Let me do one more just to make it make it clear. Um, I'm looking at this state. There's a one one in4 chance of going here. There's a one in4 chance of going back to TU.

26:18 And there's a one in two chance to go back to Tpepsilon this time. And I'm always doing my one step. [clears throat] Yep. >> The second step. Uh, there are only two possibilities. So I use write one four and then other one two I think it should be one right >> which one >> the second T one >> this one >> yeah should >> the uh this is one4 yeah you're right yeah I said the I maybe said the right thing but I wrote the wrong thing for sure >> but still I mean I'm saying it's only three possibilities so it shouldn't be one >> they're not equally no look these are two different letters so the There's always four different outcomes, but two of them do the same thing. So this this arc is much more likely to be taken >> because we're doing one step. We read one letter. So we have to count that letter.

27:23 Otherwise, uh if you leave out the plus ones, this is all going to solve to zero, right? If you finish the set of equations.

27:33 Uh okay, so we could write this all down. And we could go back to middle school and solve the system of linear equations. Boring. So, uh, I've prepared this a bit. Um, and I thought it's it's about time to also, uh, show some tools given that the module inadvertedly is classified as a practical module. Maybe that's even more fitting. Uh so I coded this up again in Mathematica and uh let me got got some AI help to translate it to simp uh but it's is really uh nice to write. So I I encourage you strongly to kind of learn these tools instead of doing stuff uh manually in in this case. So you can define uh your variables. These are exactly as I had them um they're having the same same meaning, right? And there's a cute way to do this with just from one string. That's very concise notation. Uh I mean uh in simples always have a a string representation. This is just cosmetics for us humans. You wouldn't need that for the math. And then we write down equations. Um now here's a bit of a a nuisance in simpals b you have to write it as something equals zero. and then you only give the left hand side of that. So let's pick an example that we've done. Well, the easiest ones are all the stop code on parts. They were just equal to zero. So here in this list of equations, they just show up as a term. Is this large enough to read is uh it's not showing.

29:21 Maybe just hear the browser zoom. Um we've also looked at this one the TUG this was the the bottom one where we had um the two there was this one option of going to the accepting state and there was the one in four chance of going back to TU and the one in two chance that's two times is a bit silly way to write but okay going back to the start state tpsilon okay so that's all I've done and I've done this for the other states but this is very superficially just read off from the automaton. It tells you exactly what to do. Uh then you get these equations. You have to define the set of variables again and then there's a um a function you can call to solve them. Uh so let me I might might need some time to set up uh the virtual machine. Um but then um the solution you get is essentially a map for all the symbols and we care about tapps 1 from the start state how many steps do I need?

30:28 uh then you can get a symbolic solution. Here it is. This is the map, right? You see from t you take 643 steps in expectation. It's not that much, right? Remember we had on the order of 60 from the back of the envelope calculation. In reality, it's more 21 1/3. Um and uh you can compare this with maybe some naive estimate if if you just I guess this is a um a slightly different cal well if you do the the math maybe right uh that that's another another back of the envelope calculation and this this value is much smaller that's the one thing we can take from this straight away okay now you know how to solve linear equation with a big sledgehammer of a tool. Maybe that's um not needed in this case. You would have been able to solve it manually. It's not that hard. Uh the key insight here was we can write down this automaton for these strings.

31:35 You have to work a bit to get the transitions right so that you always take a transition to the longest potential prefix of one of the codons that exist. But in this case um because they all start with a U and there's uh no other U in them the process is fairly simple. Okay.

31:59 So the biological message is it was uh 643 or it was 21. Let me cheat again. Don't want to. Yeah. 643. That's the way I learned to write it with periodic fractions. Uh so a good deal less than the 60 that we estimated from the back of the envelope calculation. Again, in this case, not a big deal because the genes are orders of magnitudes longer. But also we're uh half an order of magnitude off of our intuitive guess. So um one wants to be a bit careful with these with these calculations.