Video 6-5: §6.4 Longest common extensions (part 2)

0:00 Approximate matching

0:02 we left off last time in the middle of discussing this fifth application of suffix trees in combination with longest common extensions that is the problem of approximate matching so instead of finding exact occurrences of a pattern in the text we're now asking a more challenging question find all the occurrences of a pattern in the text where the occurrence is not exact but it might differ from the text in a certain well-defined way and the well-defined way in this case is i want the hamming distance between the two things to be at most k and what that means is just there's a at least at most k mismatched characters if i align the pattern at that position with the text so again schematically i find a position i where i can put the pattern and then it essentially occurs here exactly except maybe for k positions

1:05 uh where there's a mismatch and if i can do this then i say the hamming distance of this portion of the text and the pattern is um is two in this case because there's two places where they differ that's a simple concept it's probably the the the simplest version of approximate matching but is that's the one i'm i mean here uh so if you like it's it's searching with typos something that google became very very good at um and definitely people make more and different mistakes than just these uh replacing one character by another so in practice you will need more variations of this but we'll leave it with the simplest version for now

2:04 a second thing i mentioned last time is similar to generalized suffix trees you can also build this longest common extension data structure for several strings and you do the very same trick in this case we take the text and we take the pattern we append end of word markers different ones for the different strings so here two different ones in our case and then we just build the suffix tree and the lce data structure on this on this combined text and no other changes are necessary to this construction what that means is that we can find longest common extensions where one position is in the text and one position is in the pattern in constant time okay and uh this is uh okay let me if um

2:58 Suffix tree recap

3:01 okay maybe it's a good time to first recap this i hope you couldn't see this now i know you can rewrite but please don't um to wake you up a little bit uh i want to ask you to check all the correct statements about suffix trees so this is a lot of different statements and a subset of these will be correct this is just before we move on before we um dive deeper after this i want to see if you're up to speed with the definitions etc for the kangaroo algorithm to follow we don't really need this but for the deeper results after that we will definitely need it so it's a it's good to ask this first and maybe discuss questions before we move on with the new

4:00 material as always i'd like to see our 25 people roughly vote i've seen 28 people on the word paul so maybe we lost one or two we haven't returned from the spring break yet

4:19 but i'll leave you a little bit of time switch back maybe because here you can read all the answers it's a lot of text to read so i'll give you some more time to digest this

4:46 okay we have 25 votes uh thanks so i'll show you your results and um i should probably lock the voting now uh so um most people remembered correctly that we have to attend uh to attach this end-of-word marker um this one's an interesting one and um this has to do with this answer uh the suffix tree is a compact try of all the suffixes and not a standard tri standard tri is the one where um also the unary chains of nodes are represented as nodes and you might remember there we had an example where essentially you need a quadratic number of these nodes for the standard try but the compact tri always has linear size because it's a binary it's a tree with all internal nodes having at least two children and we have n or n plus one leaves uh we'll come to that and so the number of internal nodes is at most n so it's um therefore the the size of the suffix tree is all is always linear the quadratic is only for the standard try um yeah most people get this we don't have to store a copy of the suffix in the leaves it's enough to store the text somewhere separately and then just store and a starting index

6:22 of the suffix in the leaves the naive construction is slow that's correct it takes quadratic time because in the worst case because well we have to walk down the tree it depends what you mean by naive construction what i meant by it is take the try insert all the suffixes one after each other then each insertion takes time proportional to the length of this suffix in the worst case and that adds up to quadratic in total but it is true that we can do better we can compute it in linear time we haven't seen that yet but you have seen the claim and the last answer is almost correct but not quite it has n plus one leaves because we added this end of word marker all right thanks for voting so um here again the answer is for the record uh if there are questions about this uh please shoot them up in the q a now uh that's a good point to clarify if there's anything unclear about this um we will we will build on this but uh keep the pictures in mind the details of n and n plus one are uh usually not not that important um but of course uh we have to define it precisely so that we know what we're talking about

7:50 The kangaroo algorithm

7:53 okay good so now that we all remember and know what suffix trees look like let's move on uh we were in the middle of of this application we want to find the approximate matches of a pattern in a text and what we have is this uh magic black box that tells us if i have a position in the text and another position in the pattern what is the longest extension the longest common extension at these two positions and it can do that in constant time with that we can build the following algorithm which has become known as the kangaroo because it uh it proceeds in jumps um so first the picture again and then uh i'll walk you a little bit through the code but it's it's not really a complicated code

8:54 maybe a small sketch or an example is enough here so we're at the position that we currently try to find uh well first i should say approximate matching is complicated you uh can't expect to do this as fast as the exact matching that won't work so we're already quite happy if we can do something like the brute force algorithm except that we don't want it to be quite as bad now even a naive brute force method

9:31 would need n times m here because it's a hamming distance so we could check each of the guesses and just count how many mismatches we have so that's a remark that we can easily easily do it in n times m now if the pattern has length 100 or so if the pattern is very short maybe that's good enough but if the pattern is a bit longer and people use similar ideas for for biotic informatics applications where your text is a human genome and the pattern might be a certain mutation that is known to cause problems then this mutation encodes usually a gene that can be ten thousands of characters so m might be fairly large and then m times m is er is not efficient anymore what we will achieve is n times k and that's a different ballpark because k is uh usually very small if you if you want to find a match but half of the things don't really match that's not really useful i tend to think of k as as a small constant less than 10 or so and then this method is very efficient how does this method work it's still inspired by the brute force method we check each guess naively so we currently try to find a match of the pattern in the text

11:05 starting at position i so we have to compare these two strings and have to check whether they have hamming distance at most k or bigger than k and we use this kangaroo technique to speed up this search we take the

11:28 we start at position one in the pattern and at position i in the text that's uh how this is initialized oh sorry we start counting at zero so of course it starts at zero that's what the p says um and then uh we find the longest common extensions so we find the number of characters that match between those two that is l and we compute that using the lce data structure and now um when the lce data structure says there's four matches we already know that at position five there is a mismatch otherwise lce would have would have been bigger so we don't really have to explicitly check that fifth character we already know it's not the same so we advance both our position in the text and our position in the pattern by l plus one and we also remember that we made one we spend one of our mismatch from our mismatch budget and then we continue the next jump and maybe this gets us to here until we find another mismatch and maybe this is fine because two case is at least two and then we find a match here so of course uh where does the kangaroo come into this game it we jump from zero to this position and then to this position

12:53 so we we leapfrog over these matching parts that's where the name comes from uh how much time do we need for this we have a loop running n times roughly for all the guesses that's where the n comes from and then the k comes from the inner loop because we always increment the number of mismatches and if if we have already reached k mismatches there's no need to further compare the suffixes there won't be an approximate match in this case okay that's all i want to say about this right the pre-processing is essentially what we have to do for the lce data structure so uh behind this uh innocent term is construct the suffix tree for the two the generalized suffix tree for the two strings text and pattern compute the constant time lca data structure on top of that those two together make this longest common extension black box that's used here so this pre-processing is linear in the size of text and pattern but of course it's it's quite a complicated algorithm that's going on behind the scenes there some remarks

13:33 Applications and variations

14:21 so this is a fairly simple algorithm people found ways to substantially improve over this if if you stay with the hemming distance k you can do something like this where uh it gets easier the longer the pattern is that uses very different techniques than than this above and you can also generalize approximate match to something like edit distance where you can not only replace one character by another but you can also delete a character or you can insert one that wasn't there before that's a bit more flexible a bit closer to what people might be doing when they type on a keyboard and or honestly type something different than what they actually wanted to find

15:12 and um a last little little application is uh what we've seen with the kangaroo algorithm can also be used for matching with wild cards so in a in a very sim simple way here a wild card this is not like in in unix the star matches a single character here so you can see this is a choker character that um you can you can substitute with any character but only one that turns out to be essentially the same question as the k mismatch problem so you can solve it with a similar algorithm and get get similar running time that's that's just summing up pre-processing and the kangaroo algorithm running time but that's again uh something that is occasionally very useful and uh suffix trees make this very simple whereas if you try to do this in in a running time that's substantially less than n times m you have to be very inventive

16:21 and let me finish this section on applications of suffix trees and suffix trees plus longest common extensions with the remark that there is a classic book that i've cited before from dan gas field where he describes over 20 of these applications including these but there's 14 others that are very interesting they're more from bioinformatics that need some background to be to be useful so i excluded these but i want to stress again what a threshold concept suffix trees have been they enabled lots of applications where each of the the little application algorithms they needed slight twists etc but they're they're fairly easy to understand the real complication only lies in getting the the suffix tree constructed efficiently

17:23 Suffix tree limitations

17:27 okay that brings me to the discussion of suffix trees as we've seen them so far i've already made this advertisement it was a great leap forward they can be constructed in essentially the same time and space as storing the text or reading the text itself really remarkable

17:45 but they do have some downsides and um this is what we will uh work on next uh first of all the construction it is linear time but it's actually a substantial overhead in the sense that there is a constant attached to it it's not the same time as reading the text once it's the same time as reading the text a thousand times maybe maybe a thousand is already exaggerating but it's a substantial overhead and people have worked hard to reduce that overhead um also the construction methods that directly construct the suffix tree in linear time are fairly complicated both to understand and to implement and the last point which might be the strongest from from a theoretical perspective from a practical perspective is that suffix trees need a lot of space again they are linear in the size of the text but there is a constant attached to it it's not a thousand but it's a factor 10 or so or 20 depending on how smart you are i think you can you can achieve a factor 10 if you do it if you implement it really well with low level tricks etc and that already took people a lot of effort if you do a more careless implementation your factor will be much bigger we might

19:15 have talked about this briefly in when we discussed tries already but just remember how do you represent a single note in a try it has potentially one child for each possible character so even even if your alphabet is the ascii alphabet

19:37 the ascii characters so just the uh 128 that's our small sigma you have two options either you represent the children at each internal try node as a dictionary then you have additional overhead to search say you use a binary search tree over the uh symbols that then you don't have the constant time anymore or you represent the children in each node as an array with 128 entries and there's a pointer to that child if that exists and null otherwise but then you would have an array of 128 pointers per internal node so that's substantial overheads and there seems to be no easy way to avoid any of these downsides not both at the same time so suffix trees are great in theory but they suffer from this overhead in practice and that's what has stopped people using them in in many applications