Video 4-6: Depth-bounded search for p-ClosestString

0:02 But I thought it's nice to have a different flavor of problem. We've talked about graphs a lot. Uh so in this case we're talking about strings. Uh and it's also a problem of um of lots of practical appeal for for bionformatics applications. So this is the closest string problem. Um think of it as a consensus string. You're given some strings m a collection of m strings although of the same length. Um the problem we've actually defined earlier as one of those NP hard problems but I'm just repeating it here and we're given a a threshold K and the question is can I find some string not necessarily from the collection but any consensus that might lie in between the given strings so that the hamming distance between these uh strings is not too big at most k again hamming distance is just um you count the number of mismatch positions. So green means there's the same character and then maybe there's at other positions the strings differ and you just count the number of places where they differ. So here the hamming distance would be four. It's the simplest kind of metric on strings you could imagine. You just count how many characters are not the same. Uh and even for that the problem is already a bit tricky. So this consensus string uh you can think of these as as kind of uh genetic sequences and you're trying to find a common ancestor in in evolutionary history that is close to all of those where these might have come from. That's one way how it it might be used. Okay, that is just the number of mismatched positions.

1:58 Now how can we potentially get an FPT uh algorithm for this problem? Uh again the parameter here is is the distance. So this is more reasonable in the sense that it might be interesting in in an application to find a consensus string that's not very far away from all those strings. So K might actually be small. Uh a useful tool here is the idea of a dirty column. Uh the idea there is you line up the strings in a little in a matrix one of one below the other. And so um this is string as one s two and so on. And then you have the positions as columns in the matrix.

2:47 So that might be position zero, position one, two, three, and so on. And a dirty column is just any column where not all characters are the same. So I guess a clean column would be the same letter in all of the strings, that's clean. And anything else is dirty. So wherever you have some mismatch and it doesn't matter how many then wherever you have a mismatch that's a dirty column and if you think about it for a consensus string this is going to be the columns where I have to make a choice I can either pick in this column if I want to make all strings happy. I'm out of luck. I can only pick either an A or a B or a C to make some of the strings match with this position. But I can't do it for all of them. So the first observation is if we have many of these dirty columns, it's not going to be possible to find a consensus string. Um formally, uh what does many mean? If we have m strings of length l as before then m * k is the maximum uh number of dirty columns where we still have some hope right if if we have strictly more than these m * k columns let me maybe uh steal the picture from the previous slide Now, if you have more than uh lost the Okay, that thing's weird. Uh if I uh have more than m*s k such dirty columns, no matter what the consensus string looks like, the consensus string will have to pick a letter in each column.

5:02 And uh if there are so many dirty columns even if they if I try to distribute them according to the m strings by pigeonhole principle one string will get at least k + one. Right? If I divide this by m everyone gets a share fractionally of strictly more than k. So I will have one string no matter what characters I pick. One string will have more than k mismatches. K plus one or more. So S without an index was this consensus string or a candidate for that.

6:01 And the goal was that the distance to all the strings is at most K. So that's a no instance here. So that's my first reduction rule in the sense of kernelization. If I have uh if I have an input and I can count the number of dirty columns, if that number is more than m* k, I can immediately say no, not going to work. So far so easy. And that's mostly all we use with one tiny additional trick. Uh we're we're doing a depth firstbounded search. Again, um there will be a parameter D which is uh the number of of differences I'm still allowed. It's my budget of of uh of differences I'm I'm still allowed to make.

6:54 um if that's less than zero then I'm out of luck. If uh if I find some string according to my current string and the string and I find a string where I'm more than k plus d away. So um I'm not allowed to make more than d modifications and that even if I do all of those I'm still larger than distance k then uh it won't be possible. So why this case is correct um needs a justification. Uh the easy case is if I found my current candidate string s has distance less than k for all of the strings then I'm already happy. Then this is my consensus and I can return it. Now the usual case will be that there's at least some string where I have distance k2. Uh but hopefully um is not too far away.

7:55 And um I guess I should have should have listed call. The initial call should be with some arbitrary string say S1 and I'm starting with uh with K. So I'm allowed to make K modifications. So we'll we'll come back to justifying this this first part um on the next slide. Uh but let me explain the recursive calls first. Uh there's one more little trick there to reduce the fan out. Uh the usual cases there is some string and with the current candidate there's more than the allowed number of mismatches. So that means I have to modify my candidate string by essentially copying some positions from the string si otherwise I don't get rid of these mismatches. So the question is how many should I copy and which ones? I don't really know. Uh so first P is the set of all positions where there's a difference right where's the mismatch between current candidate and this specific string SI. And now the trick is to choose just a subset of these positions.

9:10 These are all mismatched positions. But I'm only choosing K plus one of them. I'm in this case that the distance at least is strictly larger than K. So there's at least K plus one. But there might be more than that. There might be up to 2 K initially. And the point is that I don't have to choose all of them. If it's not possible for any such set P prime with one of those positions to satisfy recursively uh the consensus string properties then I'm out of luck. I don't have to try all positions. It has to be possible with one of those otherwise I'm never going to get close enough to this string. I don't have to try all positions P only only those P prime because even if uh like a trying any of the other positions and leaving all the positions in P prime unfixed would still be too big a distance and then for all those uh we recursively try fixing that position. So we take that position in P prime. Uh we update the column P to match that string SI and then we try to recursively fix from there. So we take that new candidate and one less modification allowed. If the return value of this um ever is a a valid consensus string, it must have come from this base case and then we're happy and we return it. And if neither of these k + one options works, then we're doomed. There's no way to find the consensus. Uh and so um let me just briefly say the what the how big the search space is.

10:59 uh we're branching out with k + one here because uh that's that's the number of different recursive calls. Uh and the depth is I'm stopping when d is negative. So I I branch out with depth at most K.