Video 4-7: Depth-Bounded Search for Closest String

0:01 In the next section we look at yet another little problem that we can give a depth bounded search tree for. Uh in this case we'll end up with an even worse running time. So so far we've seen relatively small kernels and essentially singly exponential size search trees. And so maybe you get the feeling that that's all there is and so here's a little example where it's it's worse. It's a rather hard problem. Um the problem is called closest string. Um Was it in the list of NP-hard problems as well? Uh I think it was one one variant of this at least if it's not precisely the one. So what's the input? We're given strings all of the same length L.

1:02 And the question is is there a way to find uh some other string little S that is rather close to all of them simultaneously. And close here means I want a sort of consensus string S that has Hamming distance at most K at most K uh positions differ.

1:23 Hamming distance between this say if this is S then uh for every string it has to be mostly With maybe here a mismatch if there's two different characters A and B.

1:45 And so on. Uh then the Hamming distance is just the number of positions where there's a mismatch. Because the strings are all the same length the columns are perfectly aligned. So it seems a rather innocent problem if you think about it from from that perspective um why should it be so hard? But it turns out it's it's uh it's trickier than it looks.

2:11 Um some easy observations to get started. Um if we look at our M strings, it's convenient to put them in one one little a one one big matrix that has the strings as rows. And then of course it also has columns for the different positions in the string. If I have some column that contains at least two different letters, then I call that column dirty. Because it's not obvious how to deal with it, say. Let's it doesn't have a a single consensus string. That's all. And obvious first observation is if I have too many dirty columns, I'm out of luck. Simply because uh I'll by pigeonhole principle have have a problem for sure. So, bit more formally, so if I have M times K dirty columns, then um no matter what my consensus string would look like, it is a bit like a another column down here. For the consensus string, I can decide that it picks one of the two characters in each of the columns or maybe there's even more. I have to make a choice, right?

3:34 So, I'm going to I'm going to not make this be happy here. And for other choices here, maybe this one's fine. Um No, sorry, not not that one. Maybe here another string is unhappy. But it's because we have so many columns uh I will have for sure one string that is unhappy K plus one times.

4:24 >> So, I have an easy pre-processing step. If I build my matrix and just count dirty columns, if that is more than number of strings times my parameter, then I can give up and say that's unsolvable. Okay?

4:40 And that is all we need for our fancy algorithm here. Uh similar to before, we um we have our uh recursive structure. Now, this time um we also pass a candidate down that we're modifying along the way. And D is the the distance that um initially a K that we're willing to have to this string from all the others. And we initially start with just some the first string randomly as the guess for our consensus. If we're out of budget, then uh if we already have negative budget, then we're out of luck. Otherwise, let's check if we find some string um where the distance to our current S is greater than uh not just D, but K plus D. So, this is um a bit more of a uh more more more conservative, if you like. So, maybe the current string is uh not the right candidate, then it would be a bit uh premature to immediately give up just because some string doesn't have distance K to our guess initial version.

5:58 The reason why this is legit is basically on the next slide. Let me show this first. Um if you have any any two strings I and J where the distance is greater than two times K, strictly greater than two times K, then you're also out of luck. And the reason for that, let me maybe write this before we move on.

6:25 In simple terms, the Hamming distance is a metric. Full stop. That's all. Um So, in particular, um a metric means that it satisfies the triangle inequality.

6:58 So, whenever you have uh three strings X, Y, Z then the Hamming distance from X to Z is not more than the Hamming distance from X to Y and then from Y to Z.

7:23 Uh we'll we'll deal with these objects in much more generality in the bioinformatics module if you've seen that. Uh if not, um the intuition here is Hamming distance counts edit operations.

7:35 I go from I go from X to Z. As a proof idea, uh state It counts edit operations by simply replacing one character with a different one. And so, here this says the uh longest edit sequence that I need to go from X to Z is at most as bad as if I go from X to Y and then from Y to Z. Well, clearly I can just take the edit distance sequences and concatenate them and they will be valid. End of proof. Okay, this is all that's behind the triangle inequality for this. Um that directly implies this triangle inequality. And then, of course, if any two strings have uh distance strictly greater K, um their Hamming distance is, of course, not Euclidean distance, but you know, if they're strictly greater than K, if there was any string S here, that's our SI, that's our SJ. Uh where this is supposed to be both at most K, the triangle inequality would immediately contradict this.

9:02 So, this uh cannot exist where this is less than K and this is less than K. And uh that is essentially what's behind this here.

9:23 Okay. So, there's a case where we give up. Then, um if we have indeed found a candidate that is less or equal K away from all the strings, then we are happy and we return it. Otherwise, well, what's left between those two extremes? There must be a string that agrees on uh on on the that disagrees on more than K positions. So, pick any of these and let's call P the indices, the set of indices where they differ. Okay. Now, um if I want to rescue my my consensus string S, I have to change it in a couple of places to whatever SI says. Otherwise, I'm never going to make SI happy.

10:08 So, I'll have to pick a subset of these positions where I will update my S prime my my new candidate to use what S I says on these positions. Now, how many do I have to change? Uh I'll pick K plus one candidates. And then for each of them, I try whether uh fixing that position solves the problem for me. In the recursive calls, I use the new candidate where I fix a single position to whatever S I wanted. And um I've used up one budget here. Because um I'm uh I'm essentially starting from S1 initially, and K is how far can I walk away from S1? And it's clear I can never walk away more than K, otherwise I've already made S1 unhappy. So, you could say D is your your walking away from S1 budget.

11:28 Okay. And if if neither of these worked, then we can declare it's not possible. Why is K plus one here enough? Uh that will also uh use use this lemma from the next page for.

12:02 All right, let's let's first finish uh finish the analysis here while we're on this page. How costly is this algorithm? Well, here um we pick K plus one positions where we try to fix our consensus.

12:28 That's the branching factor by how many recursive calls we make. And then we do that for up to K steps deep. So, that is uh a rather large search space. Uh if you want, you can write this as K to the K. The factor plus one indeed doesn't make a difference here. Which is maybe a bit non-obvious, but as you learned when you started with asymptotics, asymptotics is all about computing limits.

12:59 So, if you take K plus one to the K and check if it is indeed big O of this, then um you obtain a limit that you should hopefully know. So, you you pull the K out, the common exponent. And within you have a a fraction that you can split, right? The K plus one over K. The whole thing to the power K. And this limit people should recognize as E, right?

13:32 Uh if you don't, there's the TCS cheat where it's it's written right here. And you can maybe for this proof even the upper lower bound is um more so than the limits. Uh you can also get a an upper and lower bound for any finite um N or K here.

14:01 >> [snorts] >> And so, this this certainly means um less than infinity. So, this is a big O of K K to the K. Right.

14:22 >> Um that we already covered. So, that was the the triangle inequality. Um that I think I argued on the side. Um the overall running time, this is the search tree is of that size. Uh then you can uh get a little bit smarter about the overall time by maintaining the distances. So, the you can maintain the edit the the Hamming distance to all the SI strings in an array so that you can check these in the initially in in constant time. Uh because you only update the candidate in in one position at a step. Um you can maintain these because you're only looking at a single character. So, you can uh speed up the computation there a bit.