Video 6-4: Tandem repeats

0:03 In the next section, uh I want to talk about tandem repeats a bit and uh these these are under the hood applying suffix trees but actually not as directly as the previous methods and that we're only using something that indirectly uses suffix trees and you've seen that before. We'll come to that. Uh before we get there, a little bit of of background and motivation and you might ask yourself what a tandem repeat even is. and I'll I'll tell you soon. And for kind of putting it a bit in context is uh we've talked about building the human's uh genome and we've talked about aligning reads to the genome to find these small uh differences where it it mostly matches but then there's a small mutation which might indicate some diseases. What else is our DNA composed of? Uh I think I mentioned this before. There's there's actually only a very small fraction of our of human DNA that encodes for proteins. That is a gene in the classical sense.

1:08 Uh 1 to 2% overall is a bit more if you count these these introns that are cut out. Uh but those are kind of arbitrary sequences. I'm sure they're not arbitrary in the strict sense, but they don't code for proteins. They don't have this u genetic code. So what's the whole rest doing?

1:29 The genes in the classic sense are only a part of what is known to be uh functional coding parts in DNA. Uh it's just that um a good other chunk and we don't exactly know how much this is for some for many parts the exact function isn't understood. So we don't know exactly where to put the the cut. But I think people are fairly fairly certain that there's a half of the DNA where we where we don't see that it does a direct function. I still find that that kind of um surprising and amusing. Uh the term junk DNA fell out of fashion but I think it it is very pointed and still uh memorable here. So we have protein coding genes as I mentioned that's the 1 to 2%. Then there's regions that code for RNA which never gets translated to protein. So RNA is not just this copy of the recipe book but rather is itself fulfilling a function as a as a bioactive molecule or even by just stopping some other messenger RNA from being translated.

2:41 Uh then there's um structural support for the DNA as a molecule itself. uh this is in particular at the end points of the chromosome. Remember the chromosomes are these wobbly things often with a a cross here. And so there's there's parts that uh hold things together and then there's parts in the middle that keep the structure. And these are special sequences in the DNA that just happen to form uh a better structure there. That's part of of of this here. There's still a lot left, right? There's still a lot of uh the other three quarters. There's fun things in there where at least partially is understood that they don't seem to have a function. There's parts of DNA that are by the the sequence they form made so that they're cut out by certain enzymes where the DNA is then joined again, but they're inserted at some other place. So, it's a cut and paste part of uh of the DNA. They're called jumping genes, but they're not actually coding for anything. They're just moving around your genome. And each time they do this, they add a tiny sequence of extra DNA where they were inserted as a leftover of the copying or the pasting process.

4:12 Fun pun. Uh then there's as I mentioned the inrons that are cut out. These are part of the genes but not part of the protein. H. And then there's pseudo genes which probably started out as ordinary genes that were copied by some process. And then one of the copies mutated into dysfunctional and was no longer used, but it was fine because the other copy still served the purpose. And so the pseudo gene was just still around. And well, if if nobody cleans up, that's what happens. Uh there's a fun species uh the lungfish, which are the the largest known genome. Maybe they're Uh that's what happens if you write papers in word. I guess if you have a proper version management system, you shouldn't have copy of copy of Gene V3 newest 2.

5:15 Now all of this uh is is somewhat amusing and you may ask uh where when do we come back to tandem repeats? The reason is that we can still it's still not uh random what happens in this uh 50% of DNA. Uh despite we despite the fact we don't know the function or don't see a function, there's structure in there that we can exploit. And in particular, you can use this for DNA fingerprinting. That's the uh at least um old school version of oh there's a blood sample on this murder place and we have a few suspects. Let's try to match their DNA to the blood we found. Um and that's going to connect to tandem repeats. So let me um move to the video there.

6:14 >> Hi, it's Mr. Anderson and in this podcast I'm going to talk about DNA fingerprinting. We sometimes refer to this as DNA profiling or your genetic fingerprint. And basically it started with this guy, Alec Jeff. Basically in his lab, he was working with X-ray and looking at um DNA. And what he figured out is he could tell a lot about a person by their looking at their DNA quote unquote fingerprint. In other words, he could see who they were related to or who they weren't. Um, he could tell paternity, for example. And so, he was working at the University of University of Leicester and basically figured out this whole idea of DNA fingerprinting. This is around 1984. And basically for the next three years, all DNA fingerprinting on the planet went through this university. And so eventually it was privatized and this is everywhere. And it'll probably eventually be replaced by just DNA sequencing. Sequencing all the letters in DNA. But to make it understandable, essentially what we have in a human is we have long linear segments of of DNA, but within that we have these genes. And so 99.9% of our DNA in everyone is going to be exactly the same. The genes are going to be the same, but again, you're going to have different copies or alals of those genes. That's what makes you you. But if we look into this area in the middle, we used to call this junk DNA, but now we know it's really important in controlling gene expression. We find that there's quite a bit of variability in here, which shouldn't surprise us because this the gene makes the protein and the protein makes the phenotype and that's really what natural selection is selecting for or against. But this in the middle can go crazy and so it does. And so an example of one that we use in DNA fingerprinting is something called short tandem repeats. Uh originally we started with something called VNTR, variable number tandem repeats. And you'll find in DNA sequencing that you have all kinds of so we had STRs, we have VNTTRs.

8:06 Before that we had restriction fragment length uh polymorphisms. And so there's a bunch of different things that we could look at, but we've kind of moved to this idea of these short tandem repeats. They work great. There's quite a bit of variability in individuals. And so what is it? You basically have letters of DNA that repeat over and over and over and over and over and over and over and over. So sometimes, you know, 50 times it repeats. And so what does that look like? Well, if we have these three individuals, we'll call this Mr. Blonde, Mrs. Red, and then Mr. Mustache. And so if we look at these three people, their genes are going to be the same, but these STRs are going to be different. These single or short tandem repeats are going to be different. You can see that Mr. Blonde has more than Mr. Mustache and less than uh Mrs. Red.

8:56 And so if I make that a little bit easier to to grasp onto, if I count them out and then remove everything else, what we get is variability between all individuals. Everything else was the same, but we see variability in here. Um, and we can cut these sections out using restriction enzymes. And then we can amplify them using polymerase chain reaction. And then we can separate them using gel electropharesis. So how does that work? Basically, I'll take the DNA and I'll put them in a little well. And so we're looking down on this. And so this is a aguros gel. I could put Mrs. Red's and then Mr. Mustache. I could put those all in DNA. Basically, I would then turn on the voltage. So there's going to be a positive charge here, negative charge up here. DNA is a negative charge. And so it's going to be pulled towards the positive. And so what's going to happen is those little fragments of DNA are going to migrate.

9:47 And so what does that allow me to do? It allows me to tell the difference between each of these individuals. And so this is their fingerprint, but you can tell that this is a really bad fingerprint because we've got some these two are exactly the same here. And so when they really do DNA profiling, what they do is they generally use 13 different sections like this. And then those 13 sections are each going to be highly variable. So it's a good way to tell who's who. When would we ever want to do this? Forensics is one reason. And then also in maternity, figuring out who's dad. And so let's talk about the murder. There was a murder that was committed. Somebody was brutally murdered by one of these three suspects. So, Mr. Blonde, Mrs. Red, or Mr. Mustache, but they left blood at the scene. And so, what I can do is I can grab samples of DNA from each of our um suspects, and then I could grab the blood itself, and then I could do DNA fingerprinting on them. So, before we separate them, you may think to yourself, which of these looks guilty? Who looks like they're capable of murder? And if we separate them then using that gel, what we can see is that Mr. Blonde is guilty. In other words, his blood matches up with the crime scene. And so how what do I mean by matching up? Well, those single or those short tandem repeats, if we look ver horizontally, are going to be exactly lined up. And if we were to look at Mr. Blond's son, we'd find more similarities than we would between the others. And so basically, that's DNA profiling, DNA fingerprinting. It's much more sophisticated than that, but again, it's kind of on its way out. We'll eventually replace this with DNA sequencing. In the US, we um the FBI has started creating this database of DNA, which is a little scary. And basically, what they use are 13 different areas within the chromosome or the genome, and then they're looking at those short tandem repeats in there.

11:40 Um, now, why do I say that's a little bit scary? I think you really want to protect your DNA because as we learn more and more about genetics, what's going to be found in your DNA? Well, predisposition to Alzheimer's or breast cancer, any of these things, which your insurance company would love to get a hold of. And so, um, and it also doesn't answer the idea of Mr. Blonde, did he really do it? I mean, did the police frame him and then contaminate the blood? Um, so we don't know that. All it does tell us is if we have two samples of DNA, the odds of two people having the same DNA fingerprint are astronomical, unless they're identical to us. But I digress. And I hope that's helpful.

12:29 Good. uh apart from the little bit of conspiracy uh feeling at the end uh it shows you that you really want to find places where you have these tandem repeats. Uh and so that's what we'll look at. Um normally a tandem repeat is just some occurrence of a string x that's followed by the same string again. Uh as in the example here there was these four letter strings. Now our assumption is we don't really know how long these are and they might be long. So given a text of n characters u find all the pairs of starting positions and lengths so that l is the length of this x and that indeed I have two occurrences right next to each other.

13:22 At first sight, um, it might it might seem dubious how suffix trees could help here because we we have the information about all the suffixes in the suffix tree, but repetitions like this xx is not so clear how you would uh find this. You could try to play games with the indices where you find things. Uh, but uh to be honest, that's not really how we use suffix trees here. Um, an efficient algorithm results via some indirect route from suffix trees. Uh, using something we've already seen and used in the last chapter, the longest common extension data structure. Uh just as a refresher um you have a string you pre-process that that string and then afterwards you can answer LCE queries which are given to positions in the text and you ask how many characters can I simultaneously read from these positions so that I see the same two strings and maybe that is immediately just superficially clear that this ought to be helpful because here I'm looking for an extension from I and I plus L Here I can ask for any kind of extensions that seems like a good match and uh we've already uh I've already mentioned this this fact that we used as a black box that you can do the pre-processing in linear time and build a linear space data structure so that LCA queries afterwards are constant time and we'll eventually get to this and it'll eventually involve suffix trees.

14:52 Uh we'll come to this soon. um the last bits of this black box will take us a bit longer. Now directly using LCE queries also seems not so clear how to do it uh because there's many many possible pairs. You could try every every combination of I of starting positions and lengths and that's going to solve the problem. Uh but it'll always take quadratic time. Now the number of such pairs could also be quadratic. So in the worst case you have to spend quadratic time if you want to list all of those pairs but these are again uh most strings will have very few of these tandem repeats. So we want an algorithm that is producing the output and of course takes the time to produce the output. Uh but apart from that uses maybe much closer to linear linear time that would be useful. Uh and certainly for genomic sequences you don't expect a ton of these uh tandem repeats. We're much much less than n squ.

16:06 The solution in this case um is is indeed a little less efficient than what we've seen so far. It's built on this idea that um if we have some seat position h that we fix and some length l that we fix then uh we can uh at distance l expect if there is a tandem repeat that somehow overlaps this seat position h then it has to occur also l positions later again. Now, we don't exactly know where it starts and we don't want to try all try out all possible ways. You you'll see in a second how we use this seat position uh to be precisely. Uh but first of all, if L and H are fixed, what you would want to do is check if there's an occurrence of X that's somehow overlapping, but it it could be moving a bit left and right. And these are all possible and and viable occurrences.

17:09 Now we can do this in constant time. Check if there are any of these occurrences using um the LCE queries. And in particular we do this one. The L1 is using the LC query on the text starting at position H and H plus L. That gives me precisely this. Now this may or may not be as big as L. If my H was the beginning of the of the repeat then it it is L and then I'm happy I found the tandem repeat already. In general my L my H might not be at the beginning of this uh X and then I have to scan left from H and H plus L to also find this matching part. And so for doing that, that's a one by the way. Let me write it like this. We kind of want the same as LC but to the left. And uh let's be lazy and just write this as to the left.

18:26 But of course, you can build this using the same LC data structure on the reversed string and flipping the indices around. So if if you're interested in the longest common extension leftwards from these two positions, you take that string, you flip it around.

18:51 So now it reads backwards and now my positions are here and here. And now I can read to the right uh as I normally would. So you can you can rewrite this as LCE on the reverse text and then something like N minus H N - H - L. So that's what we're going to do. Um what remains left is I still seem to be forced to do this for every possible age in L. So how can I make progress?

19:31 And the solution there is we use divide and conquer. In particular, if I have a string, uh there's only um four different kinds of tandem repeats that I could have. Let's pick the middle position here as a special position and call it H. I could have a tandem repeat here entirely to the left of H or here entirely to the right of H or I could have one that contains H. And there's two ways you could do that. It could be in the first X or in the second X. So one option is this.

20:13 That's essentially what's drawn here. Or you could have some U modified version of this where you have in H in the second X. That's the four types of tandem repeats I could have.

20:36 And now uh the trick is that A and B are entirely contained in the left and right half. So I'm just going to find those recursively. And for C and D, I have to work a bit harder. But at least my H is fixed. L is not fixed. So I have to look over all possible values for L. But with a fixed H and a fixed L, I can answer whether these overlap. So whether this L1 here and L2, the the important bit is that they uh touch each other or overlap and that I can test in constant time. All right. So, uh, in in its full beauty, that's what the code for this looks like. Uh, we have a, um, a recursive function where we do this uh, C and D part.

21:32 That's for checking all the tandem repeats where we have H the middle position in the first copy of X. we have to go through all possible lengths of that X and then it's a bunch of of math for computing uh the right LCE queries. So you have to kind of play this out on an example, but it's not conceptually hard. And whenever those two together when they touch or overlap, when this is at least L, then I know like in the picture here, there's an overlap. There's a way to put my X here so that from the extensions that I know about, it's covering uh the full L positions.

22:20 Um there's an out outer procedure that builds the LC data structure and uh calls these calls the recursive method and the recursive method is built so that it appends all these pairs to some output list. That's pretty much it. uh if you analyze this then the non-recursive part in in this procedure is essentially building the LC data structures and that's linear time using the blackbox of LCES that we haven't talked about but uh assuming that that works then um over all iterations or all recursive calls of this um recursive procedure we'll we're going to produce output hoods here and this is something I didn't stress here. If if we have a situation like here where uh L1 and L2 they overlap so they span more than L positions then you can actually pick any of the starting positions that are in the overlap and it's each contributing one tandem repeat which probably means that there's quite some repetition so it's not going to be very often the case because it means that uh somehow the first and last characters must be the same. Um but uh that's that's the general case. So if these overlap then for every starting position in this overlap range you have one tandem repeat.

23:49 So in in the worst case you could have n squ of these uh pairs and then you'll have to pay for it. That's why this says recording all output pairs takes uh on the order of the number of such pairs time over all the recursive rec calls combined.

24:09 But if you uh take this out then what's left of the function is a bunch of LCE calls constant time each. We do n of them in the two loops. So all of this non-recursive part on the right is linear time. That's this bit. And then the recursive function we have to set up a recurs recurrence relation. It spends linear time in each step and it does the standard style of merge sort like recurrence. So uh you'll easily see that it's n login time same as merge sort same kind of recurrence. So the total time is n login not linear but only very slightly worse right n login is still still efficient plus the output which uh usually will be