What is BLAST?

Aligning a query of $300$ residues against a database of $10^{11}$ by full dynamic programming would take $3\times 10^{13}$ cell updates per search. BLAST (Altschul and colleagues, 1990) trades a little sensitivity for a thousandfold speed by three steps: (1) list the query’s words (three residues for proteins, eleven bases for DNA) and their high-scoring neighbours; (2) scan the database for exact word matches — seeds; (3) extend each seed in both directions without gaps until the score drops a set amount below its best, keeping the high-scoring segment pairs (HSPs), then join nearby HSPs with gapped dynamic programming in a narrow band. A true homologue almost always contains at least one exact three-residue word in common; a chance resemblance rarely does, and is never extended.