Video 3-8: Linear-space alignments

0:02 Okay. Uh, one more thing that we can do to our pair wise alignments is at least save a bit on the space. So I've I've said probably quadratic time we'll have to live with unless uh you count these logarithmic improvements.

0:16 Uh but maybe we can at least improve the space which is also quadratic if you do the dynamic programming in the uh cookie cutter template way. It's actually very easy if you just care about the final edit distance as a number. because uh the next row you can do it many ways but you could say the next row that you compute it depends only on the previous row. So you store these two rows that's the very uh maximum you need and um you can uh that's clearly enough to compute the final value. So that's that's um bringing the space down to linear and you can actually do it with a single line if you remember that you're also have the dependencies uh in an orderly way. So you would only depend on this prefix of the previous table and then the more you move on the more you can delete. Sorry, you depend on the suffix of the previous table. And so you can keep writing the new table here and keep the entries from the previous row in the rest of the array. It's a bit confusing, but it's actually not uh not hard to do. So um be care for the details. They're spelled out here. uh we have a single row and depending which index we're currently in at the iteration the entry is the current row or the previous row.

1:40 Um you have to be a bit clever with keeping the entries the match entry which is the one that you're currently overwriting. So you have to keep it from uh the previous one in a local variable. But my point is uh conceptually the two lines would have been fine and that is trivial to do right there's just no point of keeping the two rows ago in memory if you only care about the the final edit distance the bottom right entry.

2:17 Now if we uh want to do the back trace that's not true right the standard back trace needs the entire table because uh at each point it asks oh where did the minimum come from in the bottom right corner fine I'm going to go diagonally up then I'm going to go there and ask where did the minimum come from but to do this check efficiently I have to know the three things that I'm uh I'm comparing so there I need the croatic space it seems Uh anyways that's true if you use the standard back tracing algorithm as it pops out of the general template but you can do better here. Uh and in a way it's again because this dynamic programming problem is so nice and structured and everything the dependencies are all very local and the idea is uh a cool chimera of dividing conquer and dynamic programming. you kind of use the two uh mixed together.

3:17 We use dynamic programming to reconstruct the edit script, but we use dynamic uh we use divide and conquer to reconstruct the edit script and we use dynamic programming to help us decide um how to break things up. So, uh I can I can try to cut a in half. So, I'm going to have my table. Uh, here's A and there's B. Um, I'm trying to find the optimal path from top left to bottom right, which is some some walk here down uh something of that sort. It will have to at some point cross the middle of A clearly. So if only I knew this point, I could independently reconstruct the top part and the bottom part. And I can even say this is restricted now to this part of the table and this is restricted to this part of the table. I might actually never need to look into this ever again.

4:30 Now we don't actually know this point in the middle, right? Um all we've done so far is compute say the score in the last row. Uh but we could make that our uh our next uh target. Um and we can use dynamic programming for that. Uh this is a standard dynamic programming task. We can separate the problem into several parts. But there's one breaking up point where we have to guess because we don't know up front a priority which um which breaking point in B we have to use. So we use dynamic programming to compute that one h how to do that also uh are we no not getting back into the same problem that we need quadratic space to find this middle point. Um and it turns out no because finding the middle point you can do with the scores or the edit distances not the back trace result. If you want to do it in just the way we've done it so far then you would need the back trace but you can work around uh in a different way.

5:40 the best break point in this in this picture. Maybe let me take that. Such a lovely drawing. Uh the best place to make this cut. And this is our J star. Uh it's it's going to be um the best way to go from the top left corner to some point here. And then the best way to continue from there and these two are summed up. That's the total edit distance. So I have to find the ch star that makes that sum minimal. I can do that if I have the entries from here to here. So the the edit distance matrix row in the middle. If I have that row, I get all the optimal edit distances from the start on the best path from top left corner to this point. That's what my score already computed. Now for the second part, this doesn't seem to work because we get all possible start points but the end point is fixed, right?

6:54 But we can uh we can just use the same computation but reverse the uh string. Reverse A and B. Then what used to be the top left become what used to be the bottom right becomes the top left. And we do the same kind of calculation. Edit distance is symmetric anyway. So it's the same whether you reverse both strings or not. Um, so there's there's nothing lost. Uh, you could have also like you could have also written separate code that works backwards. Uh, but in the in the interest of reusing code, um, I think it's more elegant to write it with the reversed strings. And so that's the final code. Um, there's some boundary conditions. what you do if uh the first string is very short and you need need that for the recursive call at some point and uh this is computing the edit script. So um in the notation we've used last time if the first string is empty all I can do to produce from the first the second string string is inserting all the characters.

8:05 Likewise if the second string is empty I'm deleting all the first characters. If this first string has a single letter then it's already non-trivial. I have to find the best place to align that character with. So I'm finding the position in B that best matches A according to my alignment score. For edit distance, it would just check if there's an occurrence of the same letter. And then I'm uh the edit script is getting rid of the first part of of B, then replacing the one we found. Um replacing from A to that letter, and then inserting uh the rest of B. >> [snorts] >> The interesting bit is if a has uh some more um than two letters then we can do a recursive call splitting a in the middle. The scores for the top part we compute with just the standard dividing dynamic programming algorithm we've seen so far. For the bottom part I'm reversing both strings. And then you have to also keep in mind to reverse the indices. So this is a bit of a you want to draw the picture and do it. Um but conceptually it's the same thing as the top part. And so by just adding those up and finding the best split point, we get our middle point. This point I star J star is then the midpoint.

9:42 So the edit script we get from this is the best edit script to get from 00 to i star jar plus the best edit script to get from i star jar to mn.

9:52 Again really think of it visually in this um in this uh graph of um points. So you have the zero up here and the mn down there. is somehow in the middle there's your I star J star and that's the best path from here to here and the best path from here to here okay um how long does this take the non-recursive cost what we do down here I mean here we have some linear cost uh that's that's uh dominated by the rest the main cost comes from these calls to computing rows because they have to fill the entire matrix. They forget most of it straight away, but they still have to compute all the rows one after the other. So these two together have theta nm cost. That's for the computation. But the space remains linear in uh in m in n sorry it's rows. So in all of this I'm I'm assuming that m is the bigger of the two strings. You can flip that if not. So we uh we get the better of the two the smaller of the two strings as the space complexity.

11:12 [snorts] So this is uh the part we have to compute in the non-recursive cost. But then I'm also recursing. Now each time I'm making a making the first string a half as long. So I can have at most log m recursive calls. So a very conservative estimate would be log m* nm right That's an n * m. But actually, if you look a bit closer, it's better than that because we get rid of a con um half of the matrix in every recursive call. That's because again my picture um if that's your optimal midpoint, the recursive calls only look at this part and this part. And that's precisely half the matrix. So by the standard geometric series, you sum up the full thing, then half the thing, then the quarter of the thing. Um for the recursive calls uh in total. So the next next one, right, will split somewhere here. So again, you're zooming in on a smaller and smaller part. And so the total size of all these parts sums to nm. So the total cost is really nm which is the same in terms of asmtoic theta class as we had for the the more space inefficient version but we at all points in time only just need a a single row or two two rows of the matrix let's say let's not get uh too catholic about this part constant number of