We saw in the previous lecture that the Burrows-Wheeler transform idea will not work unless we figure out how to invert the Burrows-Wheeler transform. Let's try to reconstruct the text banana from its Burrows-Wheeler transform, annb$aa. We know the last column of the Burrows-Wheeler matrix. We also know the first column, because the first column is simply sorting all elements of the Burrows-Wheeler transform. And therefore, we know all 2-mers in the cyclic rotations of our string. And if we sort them then we will get the first two elements in each row of our Burrows-Wheeler transform matrix. Now after we know the assorted 2-mers we once again return to the original Burrows-Wheeler transform matrix. And for each such 2-mers, they actually know the symbols that precede every 2-mer, and therefore, we know all 3-mers. We sort them and now they appear in the same order as they appear in Burrows-Wheeler matrix. We once again return to the original Burrows-Wheeler matrix, and we know again the symbols that precede every 3-mer, we'll continue. We generated all 4-mers, we sort them again, repeating the same, Thing again. And this way we generate 5-mers, we once again sort. And with the final step, we generate all 6-mer, sort them, and we now know our string, banana, banana. So we now know the entire matrix, and therefore, symbol in the first row of this matrix after the dollar sign spell banana, exactly what we need. We saw how to invert the Burrows-Wheeler transform, but it was a very memory intensive algorithm. Indeed, for reconstructing Text from the Burrows-Wheeler transform, we needed to store Text, cyclic rotations of the string Text. Can we invert the Burrows-Wheeler transform with less space and without Text rounds of sorting? To develop a faster and more memory efficient algorithm for inverting the Burrows-Wheeler transform, we'll start from an interesting observation. Let's take a look at all occurrences of a in the first column and in the last column. And let's ask a question, where is the first a in the first column? It's hiding along the circle which represent Text. And you can see that it's hiding right after panam, shown in green. So next question I want to ask, where is the first a in the last column? It's hiding along the circle. And maybe this is just coincidence, but strangely, it is hiding exactly in the same place. Let's ask the same question about the second a. And second a is hiding once again in the same position along the circle, bothe for the first column and for the last column, right after pan. The next question we will ask, where is the is hiding, and it's once again hiding in the same positions. The same here, the same here, and the same here. So it looks like that i-th position of a in the first column is hiding at the same position along the column as i-th position of a in the last column. And if we look at the appearances of n, the same rule you can check, they're the same rule will apply. So is it true in general? Let's try to answer this question. Well let's number all occurrences of a in the first column. And then let's chop off the first a, the sorted six strings that appeared in the Burrows-Wheeler transform matrix remain sorted. Because we simply remove the first identical symbol from all of them. And now let's add this chop symbol to the end of each of the strings. We added them, and of course, the strings remain sorted. But these are exactly six strings that end in a in our Burrows-Wheeler matrix. Which means that they follow in our matrix in the same order than the order we started from. And that result in the so-called first-last property of the Burrows-Wheeler transform. The k-th occurrence of symbol in FirstColumn and the k-th occurrence of the same symbol in the LastColumn correspond to appearance of this symbol at the same position of text. And it's shown in the string. Our move is the first-last property, let's try to invert the Burrows–Wheeler transform again. Let's start with the dollar sign that is located in the first row, in the first column in the first row. It corresponds to s1 in the last column. We know where s1 is located in the first column, let's move there. And s1 in the first column correspond to a6 in the last column, so let's move there. And we know where a6 is located in the first column, so let's move to this position of a6. a6 in the first column corresponds to n3 in the last column. And we know where n3 is located in the first column, so let's move here. And we'll continue moving through the matrix according to the first-last property. And slowly but surely we will be spelling our original Text. And when we finish, we notice that the memory we took is only 2 times Text. And the time we took is simply following these pointers that I defined by the first-last property. Which is also all in the length of the text. So we are done. The only question left, where is pattern matching in the Burrows-Wheeler transform?
