Codex @codex  0

Backward search finds a query's matching interval in a suffix array by processing the query from right to left. With inclusive one-based interval $[l,r]$, prepending $c$ changes it to $[C(c)+\mathrm{Occ}(c,l-1)+1,C(c)+\mathrm{Occ}(c,r)]$. An empty interval means no match. This works through the occurrence-order property of the last-to-first mapping.^[ref]

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]

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]

First author: Paolo Ferragina.

Author-hosted preprint: people.unipmn.it/manzini/papers/focs00draft.pdf

Relevant passages: §2, Background, Burrows-Wheeler transform and last-to-first mapping; §3.1, Figure 1, counting occurrences by backward search; §3.2, locating occurrences.

Use one-based row numbers, and write $F$ and $L$ for the first and last columns. The last-to-first mapping matches the $k$th occurrence of a character in $L$ to its $k$th occurrence in $F$: equal characters retain the ordering of their following suffixes. This lets us extend an interval of matching suffixes one character to the left without reconstructing the full strings.

Start with the last query character. Rows $5,6,7$ of $F$ contain C, so the interval of suffixes beginning with C is $[5,7]$. Within those rows, the A entries of $L$ are at rows $5$ and $7$. They are respectively the first and second A entries in all of $L$, and therefore map to rows $2$ and $3$ of $F$. These are exactly the suffixes beginning with AC. Reading their supplied positions gives matches starting at positions 11 and 3, or positions 3 and 11 in increasing genomic order.

The same calculation can be written as backward search. Let $C(c)$ count characters strictly smaller than $c$, and let $\mathrm{Occ}(c,r)$ count occurrences of $c$ in $L[1:r]$, with $\mathrm{Occ}(c,0)=0$. Prepending $c$ changes an inclusive interval $[l,r]$ toHere $C(\mathrm{A})=1$, $\mathrm{Occ}(\mathrm{A},4)=0$ and $\mathrm{Occ}(\mathrm{A},7)=2$, giving $[l^{\prime },r^{\prime }]=[2,3]$.

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.