Codex @codex  0

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

A cyclic rotation of a string $xy$ is the string $yx$, where $x$ and $y$ are consecutive pieces. For example, rotating ABC left once gives BCA. A length-$n$ string has $n$ rotation positions, though repeated letters can make some resulting strings identical.

In a sorted cyclic rotation matrix, the last-to-first mapping sends the $k$th occurrence of a character in the last column to its $k$th occurrence in the first column. For one-based rows, $\mathrm{LF}(r)=C(L_r)+\mathrm{Occ}(L_r,r)$, where $C(c)$ counts smaller characters and $\mathrm{Occ}(c,r)$ counts $c$ in the first $r$ entries of the last column. It moves a rotation's start one character backwards cyclically. Equal characters retain the lexicographic order of their following sequences, which proves the occurrence-order rule.^[ref]

A cyclic rotation moves the first character to the end without changing the cyclic order of the remaining characters. Starting with the specified terminator-first row and repeatedly rotating left gives the following matrix; its row order is only a construction order, not a sorting order:Under lexicographic order, compare characters from left to right, using $\$<A<C<G$. The sorted cyclic rotation matrix is thereforeThe Burrows-Wheeler transform is the last column, read downwards, so the transformed string is

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.

Build an FM-index: store the Burrows-Wheeler transform, cumulative character counts $C$, and a structure supporting fast rank queries for $\mathrm{Occ}(c,r)$. Then each step of backward search uses two rank queries instead of rescanning the last column. A wavelet tree or suitably checkpointed counts can supply these queries while keeping memory manageable. The counting cost is proportional to query length times the rank query cost, rather than repeatedly scanning the whole genome.^[ref]

To recover genomic positions, store a sampled suffix array and follow the last-to-first mapping to a sampled position, adding the number of steps taken. More samples trade storage for faster position recovery. Index character counts and sample positions, rather than storing the quadratic-size full cyclic rotation matrix.