Bowtie / BWA Indexing Engine
FM-Index & BWT Backward Search
Interactive exploration of the Burrows-Wheeler Transform (BWT), LF-mapping, and Ferragina & Manzini (FM) backward search — the sub-linear indexing framework powering Bowtie and BWA.
| Row i | SA[i] | F | L (BWT) | Suffix String |
|---|
How Bowtie & BWA Use the FM-Index
Instead of storing the multi-gigabase human genome in raw sequence form, modern aligners index it using the FM-Index. Because each backward step uses simple array lookups in $C$ and $Occ$, query searching executes in $O(|P|)$ time, entirely independent of the genome's size.
The LF-Mapping Property
The fundamental theorem of the BWT: the $i$-th occurrence of character $c$ in the Last column $L$ corresponds to the exact same occurrence of character $c$ in the First column $F$. This enables exact backward traversal without reconstructing the original text.
Sub-linear Memory & Sampling
In production aligners (like Bowtie), $Occ$ values and the Suffix Array are sampled at regular intervals (e.g. every 32 or 64 positions). This reduces the memory footprint of the 3-billion-base human genome to under 2.5 GB of RAM.