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.