Burrows-Wheeler Transformation

Abstract

The Burrows-Wheeler Transform (BWT) rearranges a text string into a completely reversible, block-sorted format that optimizes data compression and full-text indexing. When combined with an FM-Index and the Last-to-First (L2F) mapping property, it achieves the absolute theoretical limit for pattern matching: finding all occurrences of a query string in time proportional to the length of the query itself, completely independent of database size.

• Category: Block-Sorted Text Indexing
• Key Property: Reversible character clumping with Last-to-First pointer mapping.
• Search Complexity: $O(k)$ where $k$ matches query string character length.

---

Core Transformation Mechanics

The transform rearranges character arrays to group matching context symbols together. This increases compression efficiency (used in utilities like bzip2) and constructs a high-performance genomic index.

The Cyclic Matrix Generation

Using the target database example string BANANA$ (where $ represents a unique lexicographically smallest terminating character sentinel):

1. Generate Rotations: Construct all possible cyclic shifts of the source string text.
2. Sort Rows: Sort these shifts alphabetically, keeping the $ symbol as the smallest starting character.
3. Isolate the Terminal String: Extract the final column vector from this sorted rotation matrix grid. That isolated sequence forms the BWT string:

$\text{BWT}(\text{BANANA\$})=\text{ANNB\$AA}$

The Last-to-First (L2F) Mapping Invariant

The utility of the BWT rests on the Last-to-First (L2F) Property:

The L2F Core Invariant

The $i$-th occurrence of a specific character $x$ within the final column vector (the BWT) corresponds to the exact same physical character instance within the source string as the $i$-th occurrence of character $x$ inside the first column vector (the sorted alphabet list).

Because every row in the sorted matrix is a valid cyclic rotation, the character positioned in the final column always immediately precedes the character sitting in the first column in the original unshifted string text. Tracking these L2F relationships allows an engine to step backward through a sequence to reconstruct source texts without storing the full matrix.

---

Backward Search Pattern Matching

Instead of utilizing standard binary searches that narrow down ranges inside an index array, an FM-Index leverages the BWT to run a Backward Search. The matching process evaluates characters in reverse order, starting with the final character of a query string and working toward its front.

Query: [ 'A', 'N', 'A' ]  <--- Evaluated Right-to-Left (Step 3 to Step 1)
Step 1: Locate range for 'A' in First Column
Step 2: Filter matching 'N' components in Last Column boundary
Step 3: Map indices backward via L2F step adjustments

Algorithm 26 FM-Index Backward Search

procedure BackwardSearch(query, bwt, first_col)

$top \gets 0$

$bottom \gets bwt.\text{length} - 1$

$q\_idx \gets query.\text{length} - 1$

while $top \le bottom$ and $q\_idx \ge 0$ do

$c \gets query[q\_idx]$

if character $c$ exists in $bwt[top \dots bottom]$ then

$top \gets$ MapL2F(top, c, bwt, first_col)

$bottom \gets$ MapL2F(bottom, c, bwt, first_col)

$q\_idx \gets q\_idx - 1$

else

return 0

return $(bottom - top + 1)$

If the index range collapses during an iteration, the pattern does not exist in the database. If the loop finishes successfully, the remaining range boundaries identify the exact frequency and position of matching text entries.

---

Sizing and Performance Advantages

BWT-based indexing serves as the industry standard for modern sequence alignment tools (such as BWA and Bowtie) due to two distinct advantages:

• Optimal Search Throughput: Lookups execute in $O(k)$ time. Because an engine must read the $k$ characters of a query string to parse it anyway, this achieves the fastest possible complexity bound. The search cost is entirely decoupled from the length of the reference database genome ($n$).
• Compressed Footprint Bounds: The character clumping generated by the BWT can be packed tightly using Run-Length Encoding (RLE) strategies. In genomics, where vast stretches of DNA contain repetitive structural sequences, the fully functional index can require less storage footprint than the original raw source text.

---

Read Mapping Strategies Evaluation

Strategy Architecture	Preprocessing Cost	Active Search Complexity	Operational Footnotes
Aho-Corasick Automaton	$O(m)$ pattern costs	$O(n+\text{matches})$	Preprocesses read queries; best for small motif pools.
Suffix Arrays	$O(n)$ text costs	$O(k\cdot \log n)$	Leverages array binary searches on sorted index ranges.
BWT / FM-Index Engine	$O(n)$ text costs	$O(k)$	Industry standard optimization targeting massive lookups.

---

Related Notes

• Suffix Arrays
• Aho-Corasick Automaton
• Multiway Trie Implementation