LAST v418 (Short read alignment program incorporating quality scores)
The main technical innovation is that LAST finds initial matches based on their multiplicity, instead of using a fixed length (e.g. BLAST uses 11-mers). To find these variable-length matches, it uses a suffix array (inspired by Vmatch). To achieve high sensitivity, it uses a spaced suffix array (or subset suffix array), analogous to spaced seeds (or subset seeds).
The main difference of LAST from BLAST and similar tools (e.g. BLAT, LASTZ, YASS) is that it copes more efficiently with repeat-rich sequences (e.g. genomes). For example: it can align reads to genomes without repeat-masking, without becoming overwhelmed by repetitive hits.
The main difference of LAST from read-mapping tools (e.g. BWA, SOAP) is that it can find weak similarities, with many mismatches and gaps.