Video 3-5: Banded Alignments

0:02 There's one more small twist that I want to show today and that's uh modifying the problem for um an often interesting special case namely when you're only only interested in alignments that have a small distance or a high score or the statement that there is no good alignment. You just give up in this case. Um so the way to think about it in the alignment matrix first we have the two strings A and B. So A on here zero up to M B up here zero up to N.

0:58 So the problem is again the same uh setup as the original edit distance problem. And uh let's let's uh focus on edit distance. Um nothing really changes if you go to the more generalized scores that I've just shown.

1:23 So normal edit distance score and say we do just a global alignment to keep things easier. And what would we like as output? There's another parameter.

1:52 And I'm only interested in the alignment or the exact distance value if it's at most K. If the added distance of the two is at most K and otherwise you're just saying that the distance is larger and you don't have to specify anything further. You don't have to compute the exact distance and also not the alignment. I think it's natural that this is a a requirement you could settle on. Um because I said initially it's it's not a hard problem in the sense that it's polinomial time solvable. Uh if your two strings are both around a million characters maybe then uh the space already becomes a bit bit concerning like still doableish but uh it starts to get concerning. If they become even bigger, it turns into a serious problem. Uh but you may be fine to stop the whole process if the strings are really very different because you're you're looking for these conserved regions and uh if they are very different there's just nothing to observe.

3:18 Now whether you need a global alignment of these very long strings um at this point uh the details of the application um might might allow other workarounds. But let's suppose um that we're we're uh in this in this simple scenario for pedagog pedagogical reasons and we want to do uh this this task of aborting when we when we can conclude that no good alignment is possible.

3:53 As before um we have to fill this table conceptually and we have to output this value down here conceptually. Now if this value is bigger than K then we could have saved us the effort and not do it. But let's suppose um I'm trying to draw it a bit more cleanly. Let's suppose it's it's not larger than K some value D less than K. Then there's certain things that cannot happen. uh for example I think we haven't really presented alignments in this way. Um let me add that at the bottom. uh if you have an alignment matrix that you filled out during the trace back you're always following one of the three steps either top or left or uh diagonally so uh the trace back reconstructs a path through the alignment matrix by following such a such a course you can go up and left and so And it's always going to be some path that you follow. And uh the steps tell you exactly the edit operations. Right now, a good path will have to stay somewhat well, we'll have to mostly use diagonal steps that hopefully are matches, otherwise the score will be bad.

5:49 And if you look at these these paths, maybe this does fit here if I'm scaling it down a bit. The path also has to kind of reach the the top. You could say um the last few bits it can jump over. But um it has to somehow go from here to there. And if you remember how these things are defined, uh we're back to edit distance.

6:26 These are increasing only. These are contributions that count the number of edit operations. So this is a plus one in each step or a plus zero but nothing else. So if you ever reach a point where the entry is above K, this path is not going to lead to a good alignment anymore.

6:52 In particular for uh for reaching this value D, you can have steps that leave D unchanged. These must be matches. You can have a bunch of steps where you go to uh D minus one. So you had a mismatch here or insertion or deletion.

7:14 But you cannot have an unbounded number of these because they're bounded by D. And so in particular, what can never happen is that you walk very far away from the diagonal because if you did um I'm I'm trying to draw this a little cleaner again.

7:55 the difference So if if that's the main diagonal, oh god, this is uh my straight lines aren't so straight, right? If this is uh five positions off the main diagonal, then one of the strings is five characters longer than the other. At the very least, you're going to have to insert these five characters. All right. So, this is always going to be greater or equal than five because I'm doing one, two, three, four. Okay, forget about a five. It's a four. The point is every step I'm doing off the main diagonal will mean I have to have at least a four here. It could be much worse. But the point for for our application here is there's going to be a main diagonal. Let's pretend that um the distance at the end the difference between n and m is smaller than k. Otherwise, we can immediately say it's not possible.

8:56 From this from this main diagonal, we can only go uh this size k to the left and right. And anything that lies outside of this can certainly not contribute a distance less than K at the end because to reach out here this is already greater than K. It can only go up further when you continue. So it's never going to make it. What does that help? It means uh we can avoid filling the part of the table outside here. So all of this we don't have to compute and all of this we don't have to compute.

9:44 The part that we do have to compute is of size 2 * k * the smaller of the strings. And if k is fairly small, that's substantially less than the n * m we started with.

10:05 Okay, let me let me briefly summarize this and um write down uh what we learned. So by D steps implies the distance the entry there is greater equal D.

10:45 this banded matrix band of size 2k And in a way what's needed in the recurrence is to handle the boundary conditions that uh whenever you access options that would lie outside you just don't do it. And uh what's a bit annoying to implement it is uh that you somehow want to shift the indices so that it fits into a rectangular range uh rectangular array. Uh but that aside, I think the algorithm is is very intuitive. It's is not hard to modify the dynamic programming algorithm to take advantage of this bandit uh width. Um, but the code is is more messy than helpful, I think.

12:22 So whenever you access a sub problem where the difference between the the prefix lengths is too big, you just ignore that option. It will never give you something better.

12:35 And if you reach the the bottom right that way, you'll fill it with some value. Now if that value is less than K, you can trace back and you'll find an alignment. If the value is strictly larger K, then you don't have any guarantee because your uh your actual alignment might not be the best that you can find. There could be something that briefly goes out here and then back in that's better than what you found. you're kind of uh forcefully restricting your alignment to stay close to the diagonal which is okay if the final value is small but is not okay in general. So if the final entry dnm dn we don't get the correct distance. So this is not in general a replacement for the full matrix algorithm.

13:50 If it's less than K, then we get the correct value and we can trace back an alignment with that value. Uh because it the optimal one cannot leave this bandit matrix either.