Home▸Algorithms & AI▸Burrows-Wheeler Transform: The Reversible Shuffle Behind bzip2 and Genome Search

🔀 Burrows-Wheeler Transform: The Reversible Shuffle Behind bzip2 and Genome Search

Explore the Burrows-Wheeler Transform, a reversible rearrangement of a string that clusters repeated characters together, making it a powerful preprocessing step for compression algorithms like bzip2 and genome aligners like BWA and Bowtie.

Algorithms & AI3DModerate60 FPS

The simulator visually generates every cyclic rotation of an input string, sorts them lexicographically to build the Burrows-Wheeler Matrix, highlights the resulting last column as the transform output, and then walks step by step through the reversal process using the first-column, last-column relationship to rebuild the original string.

🔬 What It Demonstrates

🎮 How to Use

Type or select a sample string, then step through rotation generation to see all cyclic shifts appear, trigger the sort to watch the matrix reorder alphabetically, observe the highlighted last column as the transform, and finally press play on the reversal animation to see the original string reconstructed one character at a time using only the transform and the origin index.

💡 Did You Know?

Did you know that the same last-to-first column relationship that lets you undo the Burrows-Wheeler Transform also powers near-instant DNA sequence search? The FM-index used by genome aligners like BWA reuses this exact mapping, just to narrow down matching positions instead of reconstructing a string, allowing billions of DNA bases to be searched almost as fast as reading the query itself.

⚙ Under the hood

algorithmsdata compressionbioinformaticsstring algorithmscomputer sciencegenomicsbzip2

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install