Video 4-7: Depth-bounded search for p-ClosestString (part 2)

0:04 So where we left off um was basically the discussion of this of this uh base case where um we said if there's any string as I that differs from the current candidate by not just um k but k plus d the allowed distance plus our current budget then we can stop and maybe this is intuitive if it string is too far away. But why does this um with the initial call of a budget of K why is that correct? I mean um potentially um there might be some some other algorithm with some other way to construct a consensus where we don't walk one step one change at a time. What's behind this uh base case is this lema um which says something about the the distance of any of the strings. And here it's uh it's formulated in in this way. We're given some set of strings uh as it could be the input to our closest string problem and um a threshold k. Now if you can find any two strings in this set so that the heming distance is strictly more than two times k then there cannot be any consensus string where uh the distance to the consensus string is at most k.

1:29 And basically you can uh you can use the lema even by making this this set here uh a bit a bit smaller and kicking out one of the strings. So that here um if you have the distance between uh yeah you need it included in this statement. So that's that's the that's the more convenient statement. Now why why is this true? Um, one option would be uh if you have these uh two strings that have a distance of more than k that means they have at least k + one 2 k + one sorry 2 k + one positions where they differ. Now any consensus string um that might try to be at distance K of from both each of these positions has some character here and a different character there. So the consensus string can pick one of those two or have a third character but it cannot be the same for both. So it it could decide to copy the first string here. But no matter what you do, uh if you have two k + one red positions, you're going to pick the character from the other string in at least uh in at least k + one positions for one of the two strings. So say this is always a and b just to make the notation here easier. And no matter how you try to balance things out, maybe you go alternating between the two. Um, so this is a strange 2k + one because it's an even number. Let's add another one. And then here maybe you go back to a. No matter what you do, uh you will pick one of the strings in the majority of the cases, which means the other string has a difference to the green consensus candidate of at least k + one. And this is true no matter how you choose this green string. In the other cases, it might only get worse. another way uh to see this. So um I mean this would be this would be S. These are your SI and SJ no matter how you pick it. Another way to say the same thing is uh to say that the Hamming distance that's kind of alternative proof uh the Hamming distance is a metric. A metric is the um the minimal conditions for a for a function to serve as a kind of a distance. And so a metric has has three conditions.

4:41 Um, it needs to be greater than zero for all entries. That's obvious for the Hamming distance because it's a count. It can only count positions. So, it's never going to be negative. If you put the same string in twice, then it has to be zero. That's the other condition for a metric. And that's clearly the case because we don't have any mismatches in this between the string and itself. Uh so these are satisfied by many functions. The the crucial property of a metric is the triangle inequality. Which means uh for any x y z it has to be that the distance if you go from x to z that's not more than going from x to y and then from y to zed. And from my language um you can see how this is interpreted in terms of um distances in say the uklidian plane. If you take the distance between x and zed then uh taking the detour via y will never be shorter. Right? You can you cannot shortcut something by going a detour. But if if these distances are not defined in the usual way like the uklidian metric, it could be violated. We've discussed this in the context of the traveling salesperson problem at some point. Um now here you could you could prove that the heming distance is a metric which we u basically um have done with this picture above here. I guess uh any any kind of mismatches between the two uh you can only add more mismatches by comparing with this uh third string and then this property immediately follows because uh you take this um string as the consensus as the detour. Okay.

7:12 Um that's the justification for stopping at this at this point because the way we start is we start with one of our input strings an arbitrarily chosen one and a budget of uh k changes and here we're checking for k plus initially k so for greater than 2k um so initially that's certainly true then I I would have an instance of the lema directly Okay. Um because then S1 would differ from SI by more than 2K. Um in in the inductive steps uh you would have to uh go back um to uh to S1 by undoing the changes to see that you um if this ever fails at a later stage, you would also have some SI that differs from S1 by more than 2K positions. But we might only um if that's initially true, we will immediately stop at this point I guess. So maybe an interesting question is whether you have to do this check each time or whether it's enough to check it once at the beginning.

8:38 Um I guess it can still happen recursively that you move away from some string and then um it might cut some branches short. So it's an optimization in that case to truncate searches that are not going to succeed.

9:00 Okay, we've discussed this um last time a bit but let's let's go back briefly. Uh in the worst case this early truncation never happens say and uh we have to try all the k + one options in recursive calls and we have to go down all the way until we uh reach d less than zero. So we have a depth of K and we have a fan out of K + one. And uh what I claimed yesterday is that this is big O of K to the K. And in case you uh want a proof of that, I think that's that's actually a useful thing to know, but also a a little trick that's just convenient to do. So if you take the uh ratio and compute the limit for large k what you can do is uh pull out the power this and this this fraction or this um well I guess this term 1 + 1 / k to the power of Okay, that's something um you may have seen in the context of Oiler's number.

10:23 And just to bring back something people from efficient algorithms will know, uh there's this theoretical computer science cheat sheet, a collection of many formulas. Um sorry, I should switch over to No, you see it. Okay. um which has a lot of formulas. Uh we've used some in the past from the series. We might come back to this later. Uh there will also be one giving a representation for The thing to you should keep in mind is is probably this limit. I think this is the rest you can essentially derive from it. But the the limit of 1 + 1 / n if x is 1. 1 + 1 / n to the power n that's e that's the limit. Now conveniently it's also a strict inequality in in the case where we use it. So, uh for our limit it would have been good enough to use uh just this um so okay I'm just going to copy the formula so we have it straight where we need it. So here clearly the okay I didn't copy the limits there's a limit in front so with the limit it's I didn't switch back thanks uh there's a limit in front so the limit exactly would be e but also any of the terms is bounded by e so you could say strictly less than e and of course that's just some constant So that's order one which proves that k + 1 to the k is bigo of k to the k and that was the claim here. The search tree size is at most this in the worst case. Now you can also uh think about what's the running time of the overall algorithm.

12:52 So there's a few things we have to do here. We have to determine Hamming distances. Uh we have to find these positions where a certain string differs from the current consensus candidate. And um we have to modify strings, but that's that's uh relatively cheap.

13:13 And um with the code um as given uh you don't get the strongest bound but what you can do is overall time m * l that's the input and then plus u a factor m * k for each recursive call in the worst case and where this comes from is from the following ideas. You do a pre-processing where you read the input and get rid of u well um basically keep a list of indices of the dirty columns and you ignore the clean columns and everything that follows. The consensus can just copy the single character there. And you also reject if you have more than m* k dirty columns. That's from the previous uh lema before. So for all that follows you can effectively uh pretend that the strings have length at most m * k. Then you call this uh this method as given above and for some of the parts um you can do a bit smarter than just executing the code each time by definition. In particular you can maintain the hamming distances between the consensus string and all the strings in the input. uh then looking up a Hamming distance is constant time. Um but whenever you do a recursive call you have to update the distances. The good thing is going from S to S prime we just change a single character. So also the Hamming distance is either going to change not at all or going up by one or down by one. You just have to look at one position. So that's cheap to maintain.

14:47 uh the bottleneck seems to be to determine the positions where a specific string differs from the consensus string. Now uh thinking about this again now I think you could also try to maintain the mismatch positions between the consensus string and any of the given strings as opposed to just the heming distance. You could keep that in a linked list and you could jump to the positions. Uh you're only changing one position. So this might this might work to uh reduce the time to uh just m and not m* k here. Um but certainly what's on the slide is is doable. You can maybe improve it.

15:48 Certainly the dominating part will be the uh the exponential.