Prefix trie of T with suffix-array intervals
current entry
on the stack
expanded
pruned by D
✕ dead end
hit
The trie below contains every substring W of T. Following an edge labelled a downwards goes from W to aW, and every node stores the suffix-array interval [k,l] of its string: exactly the O(1) backward-search step of an FM-index. ^ marks that W is a prefix of T. bwa-aln reads R from its last letter to its first, walking down the trie, and tries the other letters where a mismatch is still affordable. Before searching it computes D(i), a lower bound on the mismatches needed to align R[0..i]; a branch is abandoned as soon as the remaining budget falls below D. Entries are kept on a priority stack, so the alignment with fewest mismatches is found first. Keys: → step, ← back, n next stage, f run all, r reset.