Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2025 / Paper 2 / 1 / b / Solution

To invert the Burrows-Wheeler transform, begin with six empty rows. At every iteration prepend the supplied last-column characters in their fixed row order, then sort the resulting rows in lexicographic order. After $k$ iterations the rows contain the length-$k$ prefixes of the sorted cyclic rotations. For example, the first two iterations giveEach iteration works because sorting the preceding character together with the already reconstructed prefix restores the ordering of the next-longer prefixes. Six iterations give the completed matrixThe original linear string is the unique row ending in the terminator, henceAs a check, the reconstructed matrix's final column is precisely the supplied Burrows-Wheeler transform.