FM Index visualizer — BWT, reverse transform, backward search, locate

Step through the four algorithms that together form the FM Index — the compressed text-search data structure used by short-read aligners like BWA and Bowtie2. All four share the same F/L matrix (the sorted cyclic shifts of the text + the BWT in the last column). Switch algorithms with the dropdown.

idle

F/L matrix

step through to see the per-cell computation

Result

C array — C(c) = number of chars in T smaller than c

Occ table — Occ(c, k) = #c in L[1..k]

Pseudocode


    

    

      
Used in the wild