Video 5-6: k-Mismatch Matching, Longest common extensions

0:02 For the first kind of compromise, we'll go away from alignments and instead look just at mismatches. And uh the subsection doesn't have that in the name because it's titled after the technique that we'll learn about. Um some people might know this. Uh here I'll I'll just first use it and then we'll we'll uh apply we'll see how to build the data structure that's behind this later.

0:28 So to simplify the problem, let's just look at the minimal Hamming distance instead of something like edit distance. So we go away from alignments with insertions and deletions and to alignments that only allow mis matches and mismatches. That makes the problem a good deal easier because for every starting position in the text, there's a single unique way how you could match the pattern against this. That was not the case for alignments, right?

0:56 So uh for every starting index there's exactly this one length m substring for t uh that can be irrelevant. Now you can ask this problem you [clears throat] can ask in uh in two different ways. Uh one would be you're only interested in finding one match with the minimal hamming distance among all possible matches. Or you could say I'm supplying a threshold and I want to see all matches where the Hamming distance is below the threshold. I think uh what I'm claiming here is is basically true for both versions. This is an open problem. We don't really know what the best time is to solve this in the general case of having no pre-processing done on either of the two strings. Uh there's very sophisticated algorithms that try to improve on this. Um I'm not going to explain these in more detail. Um the the tricky bit is that for exact matches you can somehow study how the pattern self overlaps and then conclude from no match in a certain position that there's not going to be a match very close because there can only be a match very close if some part of the pattern you've just looked at at this point matches the shifted pattern. That's exactly what we used in KMP that uh there has to be a certain minimum number of characters you shift the pattern before it even makes sense to check for another match. Now if you do matches with mismatches or this is a the K mismatch matching um if you do matches with Hamming distance that's no longer so clear, right? Uh it could be that you don't have a a current match here, but there's a couple of characters where you don't know because the text might differ. And then it's much less clear how much to shift further. And so there's some fairly sophisticated um studies about what you can still do in this case to shift the pattern more forward.

3:13 But I guess it's fair to say uh it's still open and there's nothing that comes close to linear time. All these methods are still involving at least the threshold for the hamming distance you're you're supplying.

3:31 What can we do? Let's start simple. Uh so again I did this in my undergrad lectures all the time. Uh you're not required to need the to to know this part. This is point just for further interest. Uh the material for our exam is what I actually explained to you or what we cover in the tutorials but not these extra things. What can we do? If I give a certain position in the text, I can compare character by character with my pattern and see if uh the number of mismatches I get is below a certain threshold. So for example, if uh I have a threshold of K mismatches and my text in my pattern, I can do the brute force string matching algorithm that tries every possible position and instead of checking that all characters match, I'm just counting how many don't and skipping ahead if there's too many. So I go through all the starting positions in the text um and all the characters in the pattern. If the appropriate characters don't match, I count that mismatch. If I reach my threshold before I'm done, I don't continue. Whereas, if I leave the loop without having seen too many mismatches, then that was an inexact match and I'm returning this one.

4:53 Instead of stopping here, you could collect them all and or keep going and return all of them. For the brute force algorithm, the running time is the same. or the the worst case running time is the same.

5:07 So that's not uh too surprising that something like this is possible. But let me point out again that this is not possible in this way for alignments because here we're really relying on the fact that you can check this single potential matching substring of T that makes this so easy. here. It could also easily be parallelized as it has a few good good properties does need extra space. Uh but it were still in the same theta class as for the alignment based methods and I claimed that it's too slow. So it still is too slow. In particular, it doesn't even depend on this parameter K. Now well we'll see soon algorithms that involve K. The point where this is interesting is that both N and M are not so small in practice. Uh N is big for sure. That's the genome and M might be a single read where it's not so big. But we want to do this for a whole bunch of reads. So the total length of all the reads is even longer than the genome.

6:10 But K, the number of mismatched characters that we would allow to still count it as a sensible match, that's going to stay small. Maybe uh a handful or so. or for the snips just one. So, it would be cool if the algorithm somehow sped up with small k, but this one doesn't.

6:35 How can we do this? Um, we're going to use a magic ingredient that for now I'm just going to show you as a definition and it'll take us a bit of time over the next week and maybe after uh the the break to establish how this works internally. That's the longest common extension data structure. Um, it does the following beat for us. We're given a string and then we pre-process we read that string and build a data structure so that after we have done this pre-processing [snorts] we can answer LCE queries which means longest common extension queries where you're given the text uh somehow and uh the input to the LC query are two positions in the text and the output of the LC query is the number of characters you can read from I and J to the right that are the same. Uh and it should be the maximum. So the next one is different.

7:40 So this length that's L the number of characters before the first mismatch. Uh that's that's what's written here formally. Now maybe uh before before we continue, how could you do this without much thinking? Whenever you introduce a problem or uh a definition like this, what's what's an easy thing you could do? For all of these data structure problems, there's two extreme solutions that you should always try just to see how bad they are.

8:18 One option is you do nothing up front and you do all the work whenever someone asks you to do the work. That's the lazy approach.

8:27 no pre-processing, but whenever someone asks you for an LC query, the only thing you you can do is start at the position I and J and read from there to the right until you fail. So the running time for that is essentially the answer of the LC query itself. It's cheap if that's short, but in in the worst case is is essentially linear.

9:08 [snorts] So clearly that's not so useful. Uh that's essentially what the brute force algorithm is already doing. The other extreme approach is premputee everything.

9:21 That's the overly eager approach. Uh we'll worry about the the pre-processing in a moment. Uh if you store it in a clever way, say in a 2D array, then the query now just is a lookup read a table entry and return the number. Uh but we have to fill this this huge table And at the very least it's going to take constant time per entry that we write because we have to keep all that information around. So first of all it's quadratic space because of the table uh I and J range over the whole length of the text and the pre-processing has to at least fill this. So it has to have at least this as time as well.

10:16 And unless you get creative and inventive, it's going to be worse than n squed time. So clearly that solution is not so uh enticing because any quadratic algorithm on a genome size data set is not going to finish or you have to work extremely hard to make that viable.

10:37 Now, the black box that I'm not going to tell you for now what it looks like internally can do a linear time pre-processing using linear space and still find the LCS in constant time. So it is strictly better than either of these extreme solutions in that it keeps the best query time and almost uh I mean the the pre-processing time was zero for the lazy approach. It's maybe hard to beat but the space still needs to store the string. So you could say it's linear in the same way. Uh and this this data structure eventually does the best of both worlds in without any compromise. So we'll alult ultimately see what this uh works like but for now let's just treat it as a blackbox result and see what we can use uh from this. So after linear time pre-processing in terms of time and space we can find longest common extensions in constant time each.

11:42 Okay. And with that we can build what's called the kangaroo algorithm because it jumps in various places. I'll I'll show it briefly. um there's something we need LCE as I defined it is on a single string so there's one text and I can have two positions in that text and then I can say how many characters are common from there on um if I if you think about the brute force algorithm for this inexact string matching we really uh can't do anything about the the mismatching part but if I have several characters that match I could use an LC query to jump over those. Uh that's what we're going to do. That's what the kangaroo jumps are. Uh but for that we need one position in the text and one position in the pattern and do LC queries across the two strings. And so at first you may wonder how that can work, but you can build a single string so that it works essentially.

12:44 Yeah, just concatenate the two. Um, but it's smart to put some some new characters in between that mark the end of either of the strings so that no longest common extension will ever run out of T into P. That would potentially be a worry if you're close to the end of T and at some point in P, you may use an extension that uses the first characters of P. Again, if you put a dollar that doesn't match any character in P, then you're safe that this doesn't happen. So we can completely ignore in the construction of LC data structures when we get to it in the future that often times you want to apply it to a set of strings not a single string. You can always do this this uh reduction step and then the same algorithm works.

13:35 So with that we get to this uh kangaroo algorithm which is really the brute force algorithm we've just seen except that it jumps over the matching parts. So much of the structure looks similar. Um but here we first jump in the two from the two positions for as many characters as we can and we increment by that many characters. Uh and I'm already adding here plus one because I don't have to check the next character. it has to be a mismatch by definition. So I can directly jump over this and count it. And so again um if I run out of budget for the mismatches then would probably be useful to have K as a parameter here. If I run out of mismatch budget before I'm done with a pattern then that's not a match and I have to continue otherwise I can return this. [snorts] uh the time for this is whatever I need for the pre-processing for this longest common extension data structure and then a loop uh that runs n times and a loop that runs at most k times.

14:43 So its overall running time n* k for the matching part that sounds not so far away from n times from from n * m but remember that k is much smaller than m. This is the number of mismatches. So maybe a handful uh whereas m was hundreds for sure. And this is indeed a useful uh a useful method if k is indeed small. This is uh it's not the worst approach. Um of course what I'm hiding here is the complexity of building this longest common extension data structure. Uh the promise will eventually come out true that it is in linear time to build this but it's not for free. So uh in particular if you look at it from this this blackbox approach um it's not clear how much we can reuse pre-processing steps uh at least the way we formulated it. You have to pre-process the entire genome and each read in each step. That sounds very expensive.

15:48 Uh but we can do this for several patterns. So in a way it's it's not an actual problem. Uh but you have to look into the the box a bit or what you can do at this level is just extend this with all the patterns that you want to process in one one go. Uh then you can make this work.