Video 6-1: Suffix trees

0:03 them. In the next unit, we'll look at suffix trees and the related suffix arrays as well uh as a means to improve upon what we've what we were able to do with exact and inexact matches uh basically by exploiting more explicitly a pre-processing step on the text. That's what we'll what we'll look at. Um the basic idea uh is is quick to explain but what we'll uh spend some time with is cracking open some of these black boxes that we find along the way where I first tell you why something is useful but then there's some complexity hidden in the parts that uh we then still have to look at. uh the context as I just said is uh we're still looking at the read mapping problem as the overarching uh application in in bionformatics that we're targeting and so far we've essentially tried to be smart with the patterns or the individual reads and we'll it's try it's time to make use of the fact that the genome the reference genome doesn't change all the time. So we can spend quite some some thinking on this once and for good. Uh if we can speed up things afterwards, that's going to be the goal.

1:27 And the first thing that we'll use for doing that are suffix trees. So let's get there step by step. We talked about tries already in the last chapter as um the starting point for the ao chorus automaton.

1:41 Uh so this I think is is the same as on that slide. I just put it there so maybe you remember. Um it's called a try even though it comes such a useful feature. Too smart. Yeah. So now you can see it again. Um, in general, tries are just a dictionary for strings where the keys are strings and you can do all sorts of things with them, whatever you would do with a dictionary or a simple table. Um, here we'll always be happy with the assumption that the strings are prefix free. This is different in the aho chorus automaton. There we cannot assume this. Uh but for this chapter, you can assume that we're all always storing strings that end with some unique symbol that marks the end of the string that doesn't occur anywhere before. And then you always have this guarantee that they're prefix free. So that no string is a proper prefix of another one because that would mean aligning this dollar sign, the end of string sign with some non end of string character.

2:51 Uh, another way to get this, by the way, is if all the strings have the same length and then also they can't be proper prefixes of each other. That's literally the example from back then when we talked about a cororus. This was fine back in the day or last week or what we wanted to do with a cororus. But you may note that there are some internal notes in this example also along these lines here that are not really serving a good purpose. They're they're only there to make the string along the path longer, but they don't serve a purpose in separating the strings that we store further. They are unary nodes of a single child. Now, that means we can store the same information with a bit less space, and that's going to be crucial for the next step. So, if you don't find this enticing for this example with just storing a random set of strings, give me a minute. Um, you can still see it as kind of a general optimization. We can get rid of all these unary nodes by just shortcircuiting the edge.

4:07 instead of going to this intermediate child will directly go to the next node. But that means I'm now forgetting that there are several characters here. So I have to do something about that. Um and what I do is that in each node I'm storing the index in the string that I'm accessing at this point. And the edges have labels that correspond to that character. For example, the root always has the zero because there's the first character that we read from all the strings. We start at zero. Remember, all indices start at zero. Now, if you follow down this right path, we skip the index one. The next branch here is looking at the character at index two. Now, if you take these two strings, BBB BBA, you see they're the same on the first two characters, as is the third here. There's nothing that starts with BA. Uh, so that's that's all we do. Uh, this has one good consequence, namely, there's no unary nodes anymore.

5:14 By definition, we've got gotten rid of all of those. So, all the remaining nodes in the tree or in the try are at least binary.

5:24 And that means you can bound the number of internal nodes uh that we have um with this usual kind of it's a similar argument as he used in the tutorial the the first problem for for this week about the graphs with degrees the handshake lema. Um we'll discuss this in the tutorials briefly next week but uh the point is all these strings eventually sit in the leaves. they have one edge going up and this edge going up has to go into some node. Every internal node I have has at least two coming in and feeds one more up. So they always reduce the number of open edges by one. So after adding at most n minus one nodes, I'm out of edges that point further up that I could attach to another node.

6:18 So in short the number of internal nodes or the number of nodes including the leaves um is linear in the number of strings that we have. The number of nodes on this left is also linear but in the length of the number the total length of all strings. Okay. Important difference here it's the number of strings. Here it's the total number of characters in all strings. Uh maybe worth like a do we have notation for this in this chapter? Maybe not.

7:15 Okay, that's the good news. The compact try is indeed smaller. Uh the bad news is I'm skipping over some characters. So I have to pay attention when I use this for searching. For example, if I look for the string B A B, I'm on this side potentially misled that uh if I check index zero, I'm happy to find a B. Then I'm checking index two and I'm happy to find a a B. And so I would declare, yeah, the strings in the dictionary, but it's not actually because it differs in the skipped character. So whenever you use search and you reach the leaf, you have to check the characters that you skipped over. That makes the code a little more complicated. It doesn't affect the overall complexity of the problem. The big O class is still the same. I can still, and maybe this is worth pointing out, search any pattern in a try of arbitrary size in time linear in the length of the pattern I'm searching.

8:15 uh I only did as many comparisons as this guy has characters. I cannot do more. And that's true in both the representations for tries, but in particular, it's still true in the compact try. This is a property we'll use over and over again.

8:35 Okay. A simp simple use of tries would already be uh an inverted index. When you have words over a text, you insert all the words of a text into a try with a reference where they occur. And then you can search in the try in time proportional to the length of the searched string and completely independent of the size of the web. For example, now we go one step further. Um, and at the first moment it might seem this has nothing to do with tries. Let me first motivate why what's coming now is indeed powerful. And let's look at this problem of the longest common substrings. You're given a set of strings and you try to find a long substring that occurs as a substring in all of these strings. For example, with two substrings here, you can try to find the longest substring that occurs in these two words. Uh what can you find?

9:38 I guess it's fairly simple because there's only uh there's so much lift. Uh there's only one occurrence here even though there's this f here. So you can extend that and you can extend it to the A. So alive occurs in both um and that should be the longest. There's I think nothing else. So it's it's in particular a substring not a subsequence, right? It's contiguous.

10:10 Now you could think about how quickly you can solve this problem. Uh I'm going to tell you a solution that's linear in the total length of all the strings. So just summing up all the characters. That's the same time as reading all the strings in up to constant factors. And uh that is not so clear like without some trick this is not going to work. Uh indeed um there's a a quote so um Don can Donald Kuth maybe you know uh from I don't know I think he wasn't mentioned in this module as the author of the art of computer programming or the author of tech a famous um founding father of many u theoretical computer science topics um he conjectured in the 1970s that this precise problem may not have a solution in linear time. And um with suffix arrays, it does uh I haven't told you what these are, but um they're essentially a way to solve this problem and many others in linear time after pre-processing. So you read the strings in building the suffix tree takes linear time and costs linear space. And based on the properties of this of this tree, you can solve lots of string problems of the sort that uh this one exemplifies.

11:44 And maybe the fact that some a now famous person was wrong about the possibility there shows you that it's doing something interesting. So what is the suffix tree is actually not a complicated thing to define. The tricky thing is just this part namely that you can build it quickly. That's the non-trivial bit. A suffix tree is nothing but the compact try of all suffixes of a text. So you take the text every possible starting position and you read from there on till the end. Um here and for all of this chapter we'll always assume the end of the [clears throat] text is marked with this end of string symbol dollar that doesn't occur anywhere before. And so we start with a text that has n characters zero up to n minus one and then the nth position is set to this dollar symbol. So um there's an example for this. Uh here's a string text and there are all the possible suffixes including the one with just the dollar.

12:53 And then you can just insert those into a try. And um this is already the compact try. As you can see from these edge labels here, there's several characters along this edge. uh that um in the computer would actually look more like uh this where you have these uh indices and just the first character as the label on the edge. Now there's another thing we can do because this is all of the strings that we store are suffixes of the same text. We can store the text once and replace these strings with just the starting index. Then I have implicitly everything I need. If I want to know what the string is that starts that belongs to this leaf, I know starting at three and reading that's going to be the string. And uh that's also what you can find here if you read from the root. However, remember what it really looks like to the computer is this. So there are some parts here where you're skipping over characters that wouldn't be represented as edge labels. So you need to store separately the text somewhere.

14:04 But we don't have to copy the text in all the leaves. These are just indices, single number. Okay. For all the explanation on the slides, we'll use this representation uh because it's more intuitive to work with where you have the entire string on the edge label. But remember for the implementation uh this is what we really store. So the number of the the space of the data structure is one word, one in one integer for each leaf, one integer in each internal node. We also store the tree structure with pointers somehow and one character per edge. All of this is is linear space in the length of the original text if I'm generous and say words of of space under the assumption that the alphabet is not obscenely big or so.

15:07 We'll not worry too much about how the suffix tree itself is represented in in or tries in general are are stored. If the alphabet were big, you'll have to think about how you do this if if there's tens of thousands of options if the character if the alphabet is really big, you might have to think about how to represent the child pointers. will not do that basically because in bioinformatics the alphabet is either four characters for DNA or maybe 20 or a few more for protein but it's not going to explode. The number of characters is going to be fine. So in the simplest case certainly for DNA you can assume that every node just has four child pointer slots and these can either be filled and that child is there or it's a null pointer. If the alphabet is huge, that wastes a lot of space because of all those null pointers. And you can start to think about how to avoid that. We're not going to do that once because the alphabet isn't so big. And second, we'll in the end get rid of the entire tree anyways.

16:10 Um this is uh the final outcome will be a different data structure. So we can uh allow ourselves to ignore that fact for now.

16:21 O okay. So that's suffix trees. It's a simple definition. Just take a text and all the suffixes throw them into a try. The tricky bit as I said is how to construct this efficiently. If you were to insert one of these suffixes after the other into a try in the natural way how you would do this on tries, then you take essentially constant time for each inserted character. But the total number of characters is quadratic because you have lots of long strings. The first half of the suffix uh of all the suffixes have at least the second half of the characters. So there you go. Your is your n squ already. And of course you can use you can compute this precisely. So that's not going to work in linear time and there's no hope to do that if you do one after the other in this way uh much faster because the intermediate try that you would get from building uh the try just has this size um that doesn't work. Now here's another magic black box that we'll eventually look into. You could do this in linear time. You can build from the text the suffix tree.

17:42 Uh and uh from what I described, think about the alphabet as constant. That's good enough. Um and you can do that in constant time in the in linear time in the end. There's actually different algorithms known for doing this. I'll I'll show you one, but there's several others that are fundamentally different. Uh it's a problem that people spend quite some time thinking about because it's so relevant in in these applications. Um and so they they came up with some uh interesting ideas along the way. It started as a mostly theoretical result but is now routinely used. Not exactly in the in the form that you build literally the suffix tree as I said but conceptually the the problem that you solve is is the same. So for the moment we'll just assume that these are already here and we'll first explore what we can do with them.