Video 5-4: The Aho-Corasick algorithm

0:03 That leaves a little bit of time for looking at the generalization of the Kuth Morris Pratt algorithm. That's the Aho Corsic algorithm. And that brings us uh a bit closer again to our original problem, namely the read mapping problem. Remember all that I've told you so far is working with a single pattern. And uh for every if I apply this to the read mapping problem, I can only do it pattern by pattern. So I take one pattern, I pre-process it into this KMP automaton, then I run the text through with this automaton and I find the occurrences. But if I have to do this for every pattern um for every read individually, I'm going to read the entire genome 200 million times, that's not going to fly. That's just too slow because P is actually the largest parameter here. Okay, m is n is a bit bigger, but p is much bigger uh than we would want it to be here. Uh it's it's going to be too slow to do p times n.

1:07 [snorts] Now much of what kmp does, in particular this clever use of failure links to keep reading one character at a time can be generalized if we are looking for several patterns in one go. So what we'll do next is build an automaton that has several that contains several patterns and uh does the same kind of job as as KMP. Read one character of the text at a time and tell me what matches are are seen so far. Uh that's what what Aho and Corsik developed. Um formally we're we're looking at the multiple pattern matching problem. So we're given a text and several patterns. Same notation as in the read mapping problem at the beginning. I just wanted to repeat the notation uh that people are are remembering. Um the patterns can have different lengths. What we'll need as well is the total length because that will pop up in the running time. Now given that input the goal is to find all matches of any of the patterns in the text. Now what this means is that we want to return these pairs uh position in the text and then the index of which pattern matches there.

2:22 So it's a concise representation um and we want to return all of those pairs. That's for the biological context. You don't want to find just the first occurrence. You want really all of them. Now the final result of this section will be that this aoreic algorithm can do m pre-processing. So the total length of the patterns and then read through the text exactly once. Um it'll have this extra cost of the size of the output because if you look at this in in the worst case you can have at every position all patterns could match. If the patterns are all A's of different numbers of A's and the text is all A's, right? Then at every position you find all the patterns. you're very happy but the output is bigger than the text is a bit of a degenerate case but to make this generally true you have to say the running time depends also on the size of the output the number of these pairs in all sensible applications this will be much smaller than n and then the dominating uh contribution is from the length of the text now for the read mapping problem the dominant contribution will probably be the pre-processing if you wanted to throw all of the patterns in at one time, but of course you can do a reasonable number of them in a batch and then go to the next.

3:49 The bird's eye overview of the Ahokoic algorithm is as follows. We built what corresponds uh in in Kuth maybe let me uh contrast what we did there. You could say we built first this this chain automaton here with just the match edges.

4:12 That was step one. And then step two was taking this and adding the failure links. Now maybe this one also uh that will also do in a cororus. What changes is that this first part is not a single chain but a try and the failure links are very similar but we do need a third component called output links or for a reason that I'll show you in an example briefly that didn't occur in KMP. So this this third step that's kind of the new bit that KMP didn't have to care about.

5:08 What do we get instead of the linear chain is uh what is also known otherwise as a data structure just for storing uh strings in general is called a try. Uh pronounced is written as in retrieval but pronounced like in try. Don't ask me why. Uh it's a way to store a set of strings so that you can efficiently find whether a string is in the set and you can do some other operations as well. That's maybe uh for us not so important. Uh here's a nicely drawn example where the strings have an additional property namely they all end with an end of string marker.

5:44 In that case they all end up in the leaves. The way a try works is that you read from the root following down some path along the edges there's characters and if you read the word from the root down to where a string ends that spells the string. So example here ab aab you read ab a b plus the dollar. Okay, if you build a try for a single string, it's just one line down. That corresponds to what we did in KMP. Okay, now the example I shown here with the dollar is a little bit of a special case. Um in general if some strings are a prefix can be a string of a prefix of another string you might also have characters or strings corresponding to internal vertices. Um because we need need an example anyways. Let me draw one and we'll take the same strings as here but without the dollar at the end.

7:11 So we'll get some root. Then there's a sub tree for everything that starts with an A. There's a substring for everything that starts with a B. Um then there's more A's, more B's. I'm not drawing this the way you would construct it when you build it. I'm drawing it so that uh the picture becomes a bit nicer for what what follows.

7:39 So it might only make make more sense um when you see the final picture. But here is the first string. If you read BBB, then you find one of the strings that we have. Um, let me not write it like this, but rather draw it as an accepting state for reasons that will very soon be very clear. Maybe you can already guess. Um, BBA is a string.

8:04 So, this is also accepting. That's BBA. Um, then we have another B at the end. That's all of those. There's three strings that start with a B. That checks out three uh of these accepting states. Uh that branch continues with an A and with a B the state and this is accepting because there's abb that's one of the strings but it also continues with another A and a B to A B AB B then ABA. Uh I can continue with AB.

9:19 That's that guy. And then we're almost done. Uh, AA is accepting. That's the first string. And then another AB. And then we're we're there.

9:38 That's a A a triple A. Okay. For the sake of the example, what you should take from this picture is uh this looks a lot like an automaton already. I can start at the root here. These edges are all directed downwards.

9:59 Some of the states are accepting, namely those that correspond to strings in the set of patterns. And I could say this is something like a nondeterministic finite automaton. If I add this loop here, so I have to decide nondeterministic. I have to guess when to start my descent into the tree. And if I guess right then I can accept some string.

10:21 How to determinize this? Again, you could say let's throw the powers set construction in general full generality on this. We're not going to do that.

10:37 The next step is adding failure links in the very same way as KMP. And uh again you could formulate this this differently. Uh let me let me put it here so it better fits there.

11:20 So it turns out the very same approach as in KMP also works. If you pretend that you do one string after the other as in KMP, you can add the failure links in the same way. Only that I'm of course following all the other edges if I have to as well. Let me do an example. Um, let's take this this one ab aab. Um, I'm doing failure links for this one. A aab. How did we do this? We got rid of the first character and see where we end up when when we read through the the string. So, I'm going to have a blue pointer marking the note I'm adding failure links from. And I'm tracking the X the failure state in red where the failure link should go to. So uh I'm I'm starting at the root. Now I read an A. That's the part I only do with the blue. Now red is still at the root because it starts with uh one letter later.

12:27 Now uh where do I put the failure link from? from the blue pointer here well to the red and indeed from the first level they will always have to go back to the root. There's nothing else you can do. Now I'm looking at the one longer prefix of my pattern namely AB. So blue has to move down to AB and X has to move down following B. So, I'm I'm going to go over here and that's where my failure link should go. So, I do that and then I do another step and I think you already see where this is going, right? Uh um next character in this pattern is an A. So, I follow down here. next character here. Oops, I can't. Ah, that's that's that's annoying. So, I would have to figure out what to do here. Um, it has to go back to the root in this case, right? There's a a vertex here. I can't read an A. So, I have to take a failure link to the root and then follow the A there.

13:59 Now what you see is that uh you want to process not one string at a time but rather prefixes of the same length. And so the real way to write this in code is to do a bre first search in the in this try. But the concept is very same as we did in KMP. And if you're willing to do the simulation step by step, you can do it without that. Let me do one example just to illustrate the concept. Um suppose now let's look at at a different string. Let's look at this uh ab bab and let's look at say the prefix that leads here. This abb. So we want the failure links from here. Okay, that's the blue guy.

14:51 Where do the failure links where does the failure link have to go to? Well, I have to read BB and BB leads me down here.

15:03 So, failure link has to go to this place. So the only tricky bit is that uh in the construction of the failure links you might rely on having the failure links on any nodes that are above on layers above.

15:24 Uh otherwise the construction is the same as for KMP. Uh if you do this every vertex here in the tree gets exactly one failure link. Um that's the same as in the KMP automaton. And uh let's maybe not do all of them. Now uh there's a second thing that can happen in this case that didn't occur in uh the KMP algorithm. And for that let me illustrate um shortly a different example that corresponds. So let's do a shorter one. the strings uh the patterns I in and tin. Maybe that's um in the interest of time I'm making the example a little shorter.

16:22 That's one string. And then there's T I N. Now the only non non uh trivial failure link is this one for I and that's going to go here.

16:45 That's going to go here. Now here's uh suppose you read in the text and you find um you find t i n t i n then you I would return the match for tin because that's what this node stands for.

17:03 But I would forget that there's also a match for in. And this could be worse in that maybe this tin is not in but is Tina. Then this would go on one more. And I would at this point say, yeah, everything's fine. That's an ordinary node. I'm not going to do anything. Uh, and I'll just continue reading but not report any match. Whereas in reality in was a match and I've missed it. That's a problem. So we can't let that happen. Uh but you can add another type of links that's the output links which effectively says if a a suffix of the string that leads to this vertex is another pattern. In this case tin is what leads to this node and a suffix in is an accepting string. I want to output this at this point. So I have a link here from this node to the longest of these patterns if there's several. And so at any point I might have to follow this chain of matches and output them right now before moving on.

18:19 Okay. Um for now maybe you can you just have to take my word that you can compute these in roughly the same way. Uh it turns out again you basically find these by from this note you have the string tin. You leave off the first character and see where that leads you. In this case it leads you right to this accepting state and it's easy. Uh if there was more than this first character that would be different then maybe you have to take some failure links. But if you if you follow this process, same kind of idea, leave off the first character, simulate where that leads you to, you automatically find the longest string that may have a match.

19:08 And here again, um you have to process the strings in a clever order. Other than that, uh you can do it in one traversal.

19:24 Okay. Um let's leave it with that. Uh that's from a bird's eye view of the a-hole corusic algorithm essentially KMP for several patterns you have to pay attention with this this new additional type of pointers because you cannot in general avoid having some patterns be uh substrings of other patterns but it works and overall time as I as I said here is linear in the patterns you can build the try in that time and you Do the addition of all these pointers in the same time with an additional traversal.