We saw that using tries dramatically improves on the brute force approach with respect to speed but becomes impractical with respect to memory. What should we do? Let's try a different crazy idea. Instead of packing patterns into a bus, let's pack text, into bus. Let me explain how we can do this. We'll generate all suffixes of text. And form a trie out of all the suffixes. It will be larger. A rather large suffix trie. For each pattern, we can check if it can be spelled out from the root downward in the suffix trie. So we are building a very large bus this time. Let's see how this idea works for panamabananas. Let's start by adding a dollar sign to the end of panamabananas and I will explain later why I add this strange dollar sign to the end of my string. So we start from the longest suffix of panamabanana$ and builds a corresponding parse in the trie continue continue continue further continue continue so far there is no branching. Continue continue and now the first branch in our suffix trie appears. Continue further there are new branches showing up and then finally be constructed something that we call SuffixTrie of text. How can we use this for part lecture? Well let's take our pattern once again, put it in the car and let's drive along the branches of our SuffixTrie. First we match first symbol in pattern. The next symbol, the next symbol. And finally, we found a match over the pattern to one of suffixes of the text to which we found a match of a pattern in the text. We use banana it will go like this. We found banana with this nab, it goes like this. Unfortunately, we didn't find it because there is no continuation for b. Let's see for antenna, we go this way and finally have to stall because there is no match for t. So it looks like this SuffixTrie idea worked for us. But there is one important question we forgot to answer. Where are the matches? How do we find our patterns match the text? There's no information in the suffix trie yet that allows us to answer this question. Here's an idea. Let's try to add some information to the leaves of our tree. But what information to add? Let's say for every leaf, let's add information about the starting position of the suffix, that generated this leaf. For example, for bananas, we will let position six, because bananas, start at position six of the text. Let's see how it works. So for panamabananas$, we will be adding zero because this suffix starts at position zero. Then we will be adding for anamabananas$ we will be adding correspondent position. Continue, continue, continue, continue, continue, continue, continue, continue, continue. And finally our tree, leafs on our tree, get decorated to this positions of the suffixes in the text and finally when we looked at all suffixes our tree got all the information we need to figure out where the positions of patterns are and that is actually what Is called SuffixTrie. Original SuffixTrie as I described earlier, decorated with the position of all the leaves in the text. However, getting information about position of suffixes to the leaves of the suffix try doesn't yet help us to figure out where the string bananas appears in the text. So, what we want to do, once we find a match, like match of bananas, we want to walk down to the leaf or maybe leaves, in order to find the starting position of the match. Let's see how it works. So for banana, we ended in the middle of the trie, but we'll continue walking, continue walking, and finally, we find where banana start at position six. For ana the continued working but there are three ways to continue working towards the leaves. This is the first one. This is the next one. And this is another one. So in this case we find that baana actually appears three times in the text and the three positions are shown on the top. So it looks like we finally solved the problem of finding positional patterns in the tree, which means we now have a fast algorithm for solving the problem. We saw that Suffix Trie results in a fast algorithm for the part I mentioned, but let's take a look at the memory footprint of Suffix Trie. Suffix Trie is formed from text suffixes of text. The average length of the suffixes is roughly text over two. And therefore, the total length of those suffixes is length of the text, multiplied by length of the text minus one, divided over two. For human genome it appears huge impractical memory footprint. Should they give up?
