BLAST-like alignment: seed and extend

Example

Reference Query Word size k Reference words Show all matching cells

1 Index: cut the reference into words of k letters and record where each word occurs (the dictionary). 2 Look up: take every k-letter window of the query and look it up; a hit is a seed. 3 Extend: a seed fixes where the query sits on the reference (one diagonal of the alignment matrix), so place the whole query there and compare letter by letter, gap-free. 4 Best hit: keep the placement with the most matches. Full DP would compare every reference letter with every query letter; seeds let BLAST look at a handful of diagonals only. Keys: → step, ← back, n next stage, f run all, r reset.

Reference (top) and alignment matrix (query down the side)

indexed reference words seed (query word found in the dictionary) matching letter pair (what a full DP would examine) seed diagonal end-to-end extension, ● match ○ mismatch best hit

BLAST-like alignment: seed and extend

Reference (top) and alignment matrix (query down the side)

Dictionary: word → reference positions (1-based)

Query words

Hits: gap-free end-to-end placements