Video 5-5: Inexact matching via alignments

0:03 In the second part of the string matching unit, we uh will start looking at inexact matches uh which is the biological more important case where uh we're finding the occurrence of a pattern in a string but it doesn't exactly match and uh what this means we already discussed a bit that there's various levels of what kind of errors uh we can allow. Uh I've just uh recaped that we had KMP aoc uh different algorithms for finding perfectly uh equal matches and again we'll take a step back from Ahok and now focus on a single pattern first and you'll see the the problem is juicy enough even even in this restricted scenario.

0:50 Uh for for the first round let's look at alignmentbased matching. So the most general version of what it could mean to match not exactly and I will call this the gold standard of uh of inexact string matching or of of read alignment in that it's the most precise uh kind of criterion for how good a match is. It misses the fewest sensible matches.

1:20 So you can think of it as an alignment as we've done in previous units. of the entire pattern and a substring of the text that we're free to choose. You'll remember what this was called, either a semi-local or a fitting alignment. Uh we had a slide that's the exact slide from back then. So we already know how to do this. It's a very a variation of the dynamic programming algorithm we've seen for alignments back then. Um and essentially we we need this dynamic programming algorithm. Um the way it's it's written here, I don't know if it's a bit too small. Uh you need the entire matrix even for at the end just picking the best column. So even if we're the best cell, even if we're just interested in the score, we would have to keep the entire matrix in memory for this version. So at least um if you're using this gold standard way of doing uh matching or finding matches in a in a text, you would at least want to slightly improve on this. Um also the running time will essentially remain at n * m.

2:38 This is hard to beat that we discussed a bit. Okay, we can shave off logarithmic factors but we discussed in the same context of these exhaustive tabulation techniques. We also discussed this conditional lower bound on uh general edit distance problems. So one thing we can do is um if uh okay I prime is used before it's introduced. Let me introduce it first. uh the fitting alignment aligns the pattern in its entirety with some some subset of the some substring of the text. I don't know just for the avoidance of doubt let's try it. So I'm ignoring this part up front but then here maybe I can spread I can have an insertion and I can mismatches and so on. I'm uh ignoring the prefix and suffix of T for free. But then in between I have to use all of the characters of P and I have to pay the general score for matches, mismatches, gaps. We don't do a fine gaps here.

3:48 I think that's not not the problem. You could generalize to that if you wanted, but let's not do that here. Um we can slightly rewrite the recursion. And the difference from the original one is here I'm uh I'm allowing at every point to start a new uh alignment. That's why this red is zero if um should this be at. Okay, it's the other way around. Ah, okay. Annoying. Let's look at this one. Uh I swap the ros of a and b. Um here I wanted T to be the string that's uh horizontal and P is the one that's that's uh vertical.

4:34 T is here and P is here. In the other chapter I had the the matrices were taller than white. So whenever I'm at the beginning of the pattern, so I'm looking at one of these cells up here, I'm allowed to start from scratch. And that means ignoring the prefix of T up to this point. Whereas if I'm in this first column, I have to pay for getting these uh this prefix of P out of nowhere. That's explaining these two columns. Now uh the previous version uh even though it's shifted um would have had uh the ending of the alignment in any of these cells in the last row. And then the last step would have been pick the best cell in the last row. Instead, let's reformulate the problem slightly so that we keep the best score while we shift right. So that the final answer will always be in this bottom right cell. And what we have to do for this is for this case where we go we only do this in the last row.

5:42 Otherwise this is um this is one and we add a gap. We're here in the cellig and now we're going from from the left, right? It's this step going, which is a deletion in T. I'm skipping a character. I'm I'm going over a character in T, but nothing happens in P. A deletion in general costs G for the gap cost, but if I'm already at the end of the pattern, I can do it for free. And with that, I'll have at some point some some cell here in the lowest row will have the best possible score. And from then on, it'll stay the same as I'm going for the right. Then at least I don't need to keep the whole matrix for just computing the best score.

6:32 And that's the prerequisite for doing the space efficient alignments we've discussed in in unit three, I think it was. Uh the rest is the same. So we can uh still we still need the same uh time complexity but for the space we can improve first of all to just compute the score we only need the last columns or maybe one column might be enough if you overwrite cleverly and you can do it with two columns for sure and you could try to use the same Dina divide and conquer algorithm to also construct the alignment from this. Remember this was the finding the best middle point. Uh I'm not going to go into this detail again. The point is that the time will stay at n * m and that's already too much. We don't really want to spend that.

7:26 Okay. Uh you don't even need to do this here. Clever. You can augment the dynamic program to store when was the last time you used this zero rule. If you store the starting point of the alignment, which is the value of I at this point in a second table, then you can just read out that second component and that's going to tell you for every score what was the starting point of the alignment or what was the prefix of t that you ignored for free. That's a nifty little optimization um that you can do here. So even without constructing the alignment, you can find all the occurrences that have or the you can find the starting index of the best occurrence. I think you only get the uh the one occurrence if you throw away the table. You could collect them all. I guess you can play further tweaks to this. Maybe it's a fun exercise problem. Um but really the point here should have been uh for our application if we were to do this for every read reading um through the entire uh the product of of the genome and the reads that's way too much.

8:44 But it seems unless we're compromising on one end we're stuck with this running time. Unless this lower bound from alignments fails. So it it seems hard to improve on this without making some compromise.