Video 10-5: Shortest Superstrings via Set Cover

0:01 In the next section, we'll see an application of set cover to uh solve a different problem. And um because we have approximation algorithms for set cover, we can then apply those to the new problem. So it is a if you like a way of a reduction. The point of this section is to show that set cover can indeed be uh used as a versatile um problem to uh embed other other kind of applications. Uh and the application we're looking at is the shortest super string problem. Uh sounds like you're looking for some uh exciting word, but uh super string is taken uh in a bit more literal form. Uh we have a some strings over an alphabet sigma denoted here by this uh set of words w1 to wn. And we're looking for a super string which is some long string that contains every string from this set as a substring. So uh for every um wi there's some range uh starting position I don't know uh uh ji up to j i plus the length of wi and that has to be wi. That's what I mean by substring just to be clear. It's a contiguous occurrence, not a subsequence where the element the letters can be spaced out.

1:31 Uh and so of course a trivial instance is to just concatenate all the strings one after the other. But the cost is the total length of the super string. And uh clearly we want this the shortest um so the minimal length. And uh how can this be shorter? Well, sometimes you can overlap certain strings. And so you can reuse characters to be part of several strings. Um, without loss of generality, we assume that neither of the words is a is a substring of another because then you can just forget about the smaller one. If it was a substring of another, it'll always be covered. So we don't have to take care of it. Um, that's just something that makes uh one specific argument in a picture a bit nicer. Uh why is this problem um interesting? It's it's an abstract representation of uh of the the DNA assembly problem. Um if you want to sequence a genome, the I mean the original version how the human reference genome was built was was more like that. Uh you can't actually read such a long uh sequence of of uh um of DNA or RNA. what you can do is is read short snippets of um uh a couple of hundred um characters whereas the overall thing has billions. So what you do is you read random substrings of the overall string many many many times and um then it's it's reasonable to assume that the shortest super string would be a reasonable way to define what the DNA originally looked like. If you have enough of these samples and they overlap by enough then um there's a hope that that's unique say now the general problem of finding the shortest super string unfortunately is nplete so you can't exactly solve this uh and uh it's an interesting question how the human reference reference genome solved worked around this problem um I suppose that they had additional lab technique tricks but there's also some some ambiguity in the reference genome left I think uh but uh for for for us all that's um relevant is this kind of picture of where the problem comes from so that it sticks better in mind uh it's it's certainly abstracted from this uh application so what does that problem have to do with set cover you may ask yourself it seems at first not like you could uh make make use of set cover here. Uh but that's what we're going to do.

4:13 And the the trick is going to be to build these uh kind of pair-wise overlaps. And I prepared this uh picture here. Um the w I'm picking two of the strings wi and wj. And now sometimes I can overlap them by a certain number of characters if these are all equal right if some some suffix of wii is the same as a prefix of wj and this can work for certain lengths maybe not all but uh it may be different lengths and I'm just taking all combinations of this and call call these these overall words so the whole the whole thing from here to here um that's that's my sigma I JL want to be a bit more precise with the length. So that's that string that's the sigma ILJ.

5:20 It's also formally defined here. Um if you prefer that um and of course yeah this this combination of three numbers is just valid if the overlapping parts match.

5:31 Now let's define the set of all those strings um where the overlap matches. And again let me stress that we include all all possible overlaps not just the the longest.

5:45 Then we can define a certain set cover instance that um is not exactly identical to the shortest superstring problem but it it uh covers uh or it it represents parts of it. Say I don't want to say something wrong here. Uh the universe is the words that we want to cover. Remember these are w1 up to wn. So we're trying to cover all the words with some super string. And the sets that we're allowed to choose from are the sets as pi where pi is a word and it's either one of the original words. I can pick them in isolation or I can pick one of these overlap pair wise overlap words with any any length of an overlap that I'm uh I want to choose. Now these are these are sets. So for each string pi the set is actually all the words that I'm covering in that string. Right? So uh pi is some string and I guess if it's exactly one of the words then there's only going to be this word that's contained in it by assumption. But for the overlap word I know there's going to be at least wi and wj. But maybe I'm lucky and there's another string that lies somewhere here.

7:12 So then all these I JK would be in S pi. Um that's the sets of our instance. Uh so this is just a fancy way of saying occurs as a substring. These I and J have nothing to do with these I and J. Uh maybe I could have picked a different different letter here. So it's just W K occurs as substring.

7:52 Okay. Um the cost of such a solution or the cost of a specific set is the length of that string. And the idea will be if we get a solution from this set cover instance then we just take as super string the concatenation of all those strings pi in any order. So you see that we're we're evading the harder part of the problem namely that we have to arrange the um the strings in some specific form. Especially it's a bit funny if you think about the DNA assembly problem. You would think that the hard part is to figure out in what order you have to put the snippets. And this set cover reduction is essentially saying, ah, I'm not going to worry about this. I'm just deciding what sets I'm going to pick. And then any order is actually equally good.

8:42 But remember that these pies um are most likely going to be from this set M. And so they contain I and J. So at least these two are put in a specific order. So we're making some progress but we're uh yeah you already see that this is not going to be an exact solution. Um maybe somewhat surprisingly you can show it's a two approximation. If you take an instance of the shortest superstring problem and we construct this corresponding set cover instance with these pair-wise overlaps um then you can show that uh indeed a bit a bit stronger you can take the set cover optimal cost and you can put that you can sandwich that between the optimal shortest superstring cost and twice that but um in in terms of an application we know that the shortest super string is np part. So we're never going to get this optimal solution here. Well, same is true for set cover, but we've seen some approximation algorithms. So we can get an approximation for the set cover optimum, then use this upper bound to get an approximation for the shortest super string problem. And for example, if you insert the specific approximation algorithm we've seen before, then you get a 2 * hn approximation for shortest super string.

10:07 I'm going to say up front this is not the best you can do for this problem. You can study this super string problem more carefully and get better better solutions better approximations. Uh but the point here is is rather to show um the versatility of set cover.

10:25 Um and I think it's um it's insightful to prove this because then you understand the reduction much better than from just the definition I've shown you. Uh the first inequality is is actually easy to see because if you take any uh super string and you um uh you arrange that then um sorry uh any any set cover solution if you arrange that if you build the the concatenation of all those pi that is a valid super string and so the best super string can only be shorter because this is a specific one and we've chosen the set cover instance so that within each of these pies in total I have to have every word covered. So that's that's all that's needed for this left inequality. The interesting part is the the second inequality.

11:26 And so for that um let's assume we have a shortest super string sar for all those words. And in general this will not have the structure that we sketch that there's an overlap only between two of the words. Uh in general this will look different. In particular um I'm going to draw a picture on the next next page. Then um so it's I'm going to draw it in in big the next on the next page. It's one long string and it will it will have certain of the words occur in a certain order.

12:06 So that's W1 W2 and so on. They all have to occur there somewhere. By how much they overlap we don't know. We certainly know there can't be a position where I'm not overlapping with any word because I could just strike out that character. So there will be some order in which these strings occur. And now this is where the assumption from earlier comes in. uh this one um if no sub no string is a substring of another that means the order in which they start must be the order in which they end in s star at least they cannot I take that back but uh they can't um they can't be contained within another so the I guess I could have such a case but the starting point. Um we'll number them by the starting point. That should be good enough.

13:14 Okay. To further analyze this um we need to uh define some uh some groups here. So this is uh our super string. And so um there's some first word here and then maybe overlapping that is another word. Maybe it comes a longer one maybe um shorter but it always has to reach behind the stopping point of the previous one.

14:05 Maybe that's enough. Maybe I'll put one more. Okay, this can't exist. Must be overlapping here and so on. Now observe um I can always say uh I'm I'm explaining the definition up here but in in pictures. So there's uh a first word that starts a new group. That's the word uh the index i1. And then there's there's going to be a number of words that overlap this uh first word or specifically the the uh ending indices. Uh and then at some point I'm uh entirely behind this first one. So uh I'm I'm defining a group to end with this uh overlap here. So the last word that still has something in common with this first one, that's going to be the end point of that first group.

15:08 And so there could be an arbitrary number of other words in between that I don't know about. Uh sorry, this is stopping here. Ah, you know what? Let's cheat a bit. So the point of of this definition of course is that if I take the substring of my super string up to here, that's going to be one of my sigas. It's uh okay, we'll have to give this a name. I think I just called it uh the previous. So this is I 2 minus one. Fine. So it's going from I1 up to I 2 -1. And there's some certain overlap. I don't know how long that is, but that's a certain length. So that's my L here. So I I can uh describe some part of this super string as a sigma JL. Okay, great. I can of course do this with the next group as well.

16:25 And I can keep going on like this. Um, so this one ends here. And then we have this overlap up to there. It's a long guy. Um, this one starts a new group. This one's a group of its own.

16:48 It's probably useful to have a little space here. The um just going to sketch this guy here. Now the key observation is that these light blue guys overlap and so they're not going to correspond to my set cover instance because in the set cover instance I'm just taking the concatenation of these pies. So uh it looks like we're screwed but we're not entirely screwed because it can't be that the blue light blue guys overlap between one group and two further groups. If I uh go to the next group, I might have an overlap because there's this this blue part here that's sticking into the next red word. But then when this group ends, that means the starting point here has to be behind the end point there. Otherwise, this would still be part of the group. So, or say it again, um the starting point here has to be behind the end point there. So there's going to be some continuation until here. So the starting point here, the end point here has to be behind that end point. I don't know. So there's a a gap between these two. The end point here is behind that guy. Which means the starting point of this last guy has to be here. And if you look at group three, it cannot start before this end point.

18:25 Otherwise, it wouldn't start a new group. And that endpoint cannot be before this endpoint otherwise uh we would have included it. Um so otherwise this would be contained in that string. That's our assumption. So if I go from group one to group three the light blue guys cannot touch. They cannot overlap. They can touch but they cannot overlap.

18:54 Okay, keep that picture in mind because it's going to go away. Uh so group J starts at this and ends at this. That's what I've just drawn. And we can define these light blue overlap strings. Um the groups can overlap. So their concatenation might be longer than the super string. But uh whenever I jump to the next the next group um I get that they don't overlap which means um if I uh if I do take my light blue guys and I'm concatenating them all I'm going to at most cover these optimal superstring twice once with the odd and once with the even pies. case and so that's why the the total length is almost twice the optimal one. So in a way the um the set cover approximation here is useful in that it's is only a two a factor two away. The tricky bit is to get a good solution for set cover which is itself uh hard to approximate with a good good factor.

20:07 uh but it it certainly can can model this problem to a to a reasonable degree and as I mentioned you can do better if you study this problem in uh exploit its its specific properties more.