Slide deck
BackSeven sequence aligners, three jobs
Seven well-known sequence aligners do three jobs. BLASTN, BLAT and LAST search for local similarity and differ mainly in their seeds; BWA-MEM and Bowtie2 map reads onto an indexed genome; CLUSTALW and Clustal Omega build multiple alignments, Clustal Omega at far larger scale.
Sequence alignment · sources read 17 October 2026
Sequence aligners explained
LAST · CLUSTALW · Clustal Omega · BWA-MEM · Bowtie2 · BLASTN · BLAT
Alignment strategies compared1 / 15
Overview
Three jobs, seven tools
This article’s grouping; each tool’s documentation describes only itself.
Search
Find where a sequence matches a database or genome
- BLASTN · BLAT · LAST
Map reads
Place millions of sequencing reads on a reference genome
- BWA-MEM · Bowtie2
Align many
Line up many related sequences in one alignment
- CLUSTALW · Clustal Omega
Seven sequence aligners · sources read 17 October 20262 / 15
Basics
Alignment in one picture
Query
ACGTTGCAATagainst referenceACCTTGCGAT: 8 of 10 positions match, which is 80% identity.Local
Only the best-matching stretch is reported
- BLASTN and LAST work this way.
End-to-end
Every position counts
- Bowtie2’s default; the Clustal tools align full length.
Gaps
An insertion or deletion costs an opening plus an extension penalty
- Called affine gap costs.
Seven sequence aligners · sources read 17 October 20263 / 15
Basics
Seed, then extend
BLASTN, BLAT, LAST, BWA-MEM and Bowtie2 follow this pattern and differ mostly in the seed step. CLUSTALW and Clustal Omega build a guide tree instead.
- 1SeedFind a short exact match through an index
- 2ChainGroup seeds that line up
- 3ExtendGrow each seed with dynamic programming
- 4ScoreKeep alignments that score high enough
Seven sequence aligners · sources read 17 October 20264 / 15
Seeds
Seeds at a glance
Longer seeds run faster but miss weak matches; shorter seeds catch more and cost more time.
Tool Seed Index BLASTN Exact words: 28 bases (megablast, default), 11 (blastn) Query word table BLAT Two perfect 11-mers on one diagonal Genome 11-mers in memory LAST Adaptive: grown until rare Suffix array BWA-MEM Supermaximal exact matches, at least 19 bases FM index Bowtie2 Fixed, 22 bases (20 in local mode) FM index Seven sequence aligners · sources read 17 October 20265 / 15
Search · 1 of 3
BLASTN
Fixed word seeds, X-drop extension, and an E-value for every hit
- 1Cut the query into words28 bases (megablast) or 11 (blastn)queryGATCCTAGGCTTACGATCCTAGGCT1 ATCCTAGGCTT2 TCCTAGGCTTA3 CCTAGGCTTAC4
14 bases give 14 − 11 + 1 = 4 words of 11, each filed in the lookup table under its query position (blastn task).
- 2Extend each hitUngapped X-drop, then gappedqueryGATCCTAGGCTTACGATGCAsubjectGATCCTAGGCTCACGTCCAG
N seedN matchN mismatchN dropped
+2 a match, −3 a mismatch. The best score, 25, is reached after 15 bases; at 19 the score is more than X = 5 below it, so the extension stops and is cut back to 15. X here is a toy value.
- 3Score and rankKarlin–Altschul statistics give E-values
Hit Match / mismatch Score A 14 / 1 25 B 13 / 1 23 C 11 / 0 22 Each hit scored +2/−3. An E-value counts the chance hits expected to score at least as well, so it falls as the score rises and the ranking is the same. Hits with E above 10 are not reported.
Fact Value Index Query word lookup table Seeds Exact words of 11 or 28 bases; 7 for short queries Confidence E-value and bit score Best for Divergent DNA, with statistics Seven sequence aligners · sources read 17 October 20266 / 15
- 1Cut the query into words28 bases (megablast) or 11 (blastn)
Search · 2 of 3
BLAT
Index the genome, scan the query: fast placement of near-identical sequence
- 1Index the genomeNon-overlapping 11-mers held in memorygenomeTGGACCTAGCAATCGGTACCATTGGACCTAGCA1 ATCGGTACCAT12
22 bases of genome go into the index as 2 non-overlapping 11-mers, not as the 22 − 11 + 1 = 12 overlapping ones. The number is where each starts.
- 2Require two hitsTwo perfect 11-mers on one diagonalCTGGACCTAGCAATCGGTACCATG TGGACCTAGCA−1 ATCGGTACCAT−1
N seed
Every 11-mer of the query, the top row, is looked up. Two hit the index, both on diagonal −1 (genome position minus query position), so the region goes on to be aligned.
- 3Stitch the blocksExons joined into gene-level alignments, splice sites adjustedgenomeATGCCAGTAAGCAGGTTCGAmRNAATGCCA--------GTTCGA
N match- gap
Two 6-base blocks are joined across an 8-base gap; the gap’s GT…AG ends fit a canonical splice site.
Fact Value Index Genome 11-mers in memory (about 1 GB) Seeds Two perfect 11-mer hits Confidence Score and identity; no E-value in the default output Best for mRNA on a genome at 95%+; UCSC pages quote a minimum of 25 or 40 bases Seven sequence aligners · sources read 17 October 20267 / 15
- 1Index the genomeNon-overlapping 11-mers held in memory
Search · 3 of 3
LAST
Adaptive seeds, for repeat-rich genomes and whole-genome comparison
- 1Build a suffix arraylastdb indexes the reference onceACG5ACGTACG1CG6CGTACG2G7GTACG3TACG4
The 7 suffixes of the reference ACGTACG, sorted. The number is where each starts; one lookup finds every suffix that begins with a given seed.
- 2Grow adaptive seedsEach seed lengthens until it is rare in the referencequeryACGTTCA
Length Seed Occurs 1 A 2 2 AC 2 3 ACG 2 4 ACGT 1 N seed
The seed grows a letter at a time until it occurs at most m = 1 times in the reference: a 4-letter seed. m here is a toy value.
- 3Extend, then learnGapless then gapped X-drop; last-train learns rates from the dataref.TCACGTTGGATCAAqueryTGACGTTGGA-CTA
N seedN matchN mismatch- gap
The core, the longest identical run (8 letters), seeds a gapped extension to either side. Its 2 substitutions and 1 deletion are the kind of difference last-train learns rates from.
Fact Value Index Suffix array (lastdb) Seeds Adaptive, grown until rare Confidence E-value and EG (expected hits per billion query letters) Best for Repeat-rich or divergent genomes Seven sequence aligners · sources read 17 October 20268 / 15
- 1Build a suffix arraylastdb indexes the reference once
Map reads · 1 of 2
BWA-MEM
Maximal exact matches as seeds; local or end-to-end chosen automatically
- 1Find maximal exact matchesSMEMs of at least 19 bases; long ones re-seededref.ACGTTAGCCATGGACTTGCAATreadACGTTAGCCATGGACTTGCAGTACGTTAGCCATGGACTTGCA20 AG2 GT2
N seedN matchN mismatchN dropped
3 SMEMs cover the read; the number is each one’s length. Only the 20-base SMEM reaches the minimum of 19 and becomes a seed; none is over 28, so none is re-seeded.
- 2Chain and extendBanded affine-gap dynamic programming with Z-drop
Seed Read Ref. Length A 1–20 101–120 20 B 22–45 121–144 24 C 27–45 5001–5019 19 A and B lie in order on read and reference: one chain. Its one extra read base is a gap costing 6 + 1 = 7, so with 1 per match it scores 44 − 7 = 37. C’s chain sits inside that read span and scores 19, so it is filtered out.
- 3Pair and reportMates rescued within the insert-size range; MAPQ output
Window Bases μ ± 4σ 200–400 With an insert mean μ of 300 and spread σ of 25 (toy values), an unmapped mate is searched for within 200–400: one at 350 is rescued, one at 450 is not. MAPQ is Phred-scaled: 30 means a 1 in 1,000 chance the read is placed wrong.
Fact Value Index FM index (bwa index) Seeds SMEMs, at least 19 bases Confidence Mapping quality (MAPQ) Best for Reads or contigs from 70 bases to megabases Seven sequence aligners · sources read 17 October 20269 / 15
- 1Find maximal exact matchesSMEMs of at least 19 bases; long ones re-seeded
Map reads · 2 of 2
Bowtie2
Several fixed-length seeds, then SIMD-accelerated extension
- 1Pick seeds from the read22 bases (20 in local mode), from the read and its reverse complementreadTTGCATCCTAAGTCTAGCTTGATTGCATCCTA1 CCTAAGTCTA7 TCTAGCTTGA13
Seeds of 10 every 6 bases (toy values) give 3 from a 22-base read, and 3 more from its reverse complement. By default a seed is 22 bases (20 in local mode), taken every 1 + 1.15√L bases of an L-base read.
- 2Look them upThe FM index finds exact, ungapped hitsref.TTGCATCCGAAGTCTAGCTTGATTGCATCCTA0 CCTAAGTCTA0 TCTAGCTTGA1
N seedN matchN mismatch
A seed must match exactly (-N 0); the number is its hits. The mismatch at base 9 breaks seeds 1 and 2, and seed 3 finds its 1 hit.
- 3Extend with SIMDPrioritised hits get SIMD-accelerated dynamic programming
Mode Score Minimum End-to-end −17 −30.6 Local 81 51.3 A 50-base read with one mismatch (−6) and one 2-base gap (−11). End-to-end starts from 0; local adds +2 for each of the 49 matching bases. Both clear their minimum, −0.6 − 0.6L and 20 + 8 ln L.
Fact Value Index FM index (about 3.2 GB for the human genome) Seeds Fixed, 20–22 bases, no mismatches Confidence Mapping quality (MAPQ) Best for Reads of about 50 to a few hundred bases Seven sequence aligners · sources read 17 October 202610 / 15
- 1Pick seeds from the read22 bases (20 in local mode), from the read and its reverse complement
Align many · 1 of 2
CLUSTALW
The classic progressive multiple alignment
- 1Measure distancesEvery pair aligned, by k-tuples or full alignmentAGATTACAGCABGATTACTGCACGACTTCAGGADGACTTCTGGT
A B C B 0.1 C 0.3 0.4 D 0.5 0.4 0.2 Distance is 1 − identity: A and B differ at 1 of 10 positions, so 0.1.
- 2Build a guide treeNeighbour-Joining orders the sequences
Neighbour-Joining on those distances pairs A with B and C with D; the root goes at the mid-point of the longest path.
- 3Align along the treeWeighted profiles, position-specific gap penaltiesAGATTACAGCA1BGATTACTGCA1CGACTTCAGGA2DGACTTCTGGT2
N match
Joined in the tree’s order: 1 A with B, 2 C with D, then 3 the two profiles with each other.
Fact Value Index None (all-pairs distances) Seeds None (a distance tree instead) Confidence None Best for Small sets, teaching, reproducing older work Seven sequence aligners · sources read 17 October 202611 / 15
- 1Measure distancesEvery pair aligned, by k-tuples or full alignment
Align many · 2 of 2
Clustal Omega
Scalable multiple alignment, profile HMM against profile HMM
- 1Embed the sequencesmBed: distances to about log N reference sequencesS1GATTCAGC0, 0.5S2GATTCTGC0.29, 0.5S3GACTCAGC0.29, 0.33S4GTCTAGC0.5, 0S5GTCTATC0.67, 0.33S6GTCTAGG0.67, 0.17
Each sequence becomes its distances to n = 2 reference sequences, S1 and S4: 6 × 2 = 12 distances instead of all 15 pairs. The distance here is the share of 2-letter words not in common, a toy measure.
- 2Cluster into a treeK-means or UPGMA, O(N log N)
UPGMA on those vectors puts S1–S3 in one group and S4–S6 in the other.
- 3Align HMM to HMMHHalign at each node; iteration optionalS1GATTCAGCS2GATTCTGCS3GACTCAGCS4GTCT-AGCS5GTCT-ATCS6GTCT-AGG
- gap
Each group is a profile; the two are aligned column to column, and a gap opens at column 5 of the second.
Fact Value Index None (mBed vectors) Seeds None (a clustered tree instead) Confidence None Best for Small to very large sets; over 190,000 sequences in its authors’ test Seven sequence aligners · sources read 17 October 202612 / 15
- 1Embed the sequencesmBed: distances to about log N reference sequences
Side by side
Seven tools, side by side
MAPQ is a mapping-quality score, not an E-value.
Tool Job Index Seed Confidence BLASTN Search Query word table Exact word, 11 or 28 E-value BLAT Search Genome 11-mers in memory Two 11-mers Score, identity LAST Search Suffix array Adaptive E-value, EG BWA-MEM Map reads FM index SMEM, 19+ MAPQ Bowtie2 Map reads FM index Fixed, 20–22 MAPQ CLUSTALW Align many None None None Clustal Omega Align many None None None Seven sequence aligners · sources read 17 October 202613 / 15
Choosing
Which one should I use?
Readings from the comparison, not rankings.
Your situation Suggested tool Short reads, about 50 to a few hundred bases BWA-MEM / Bowtie2 Long reads or assembled contigs BWA-MEM, or LAST with last-train mRNA on its own genome at 95%+ identity BLAT Divergent homologues that need E-values BLASTN Whole genomes with many repeats LAST Multiple alignment of many sequences Clustal Omega Seven sequence aligners · sources read 17 October 202614 / 15
Take-aways
Pick the job first, then the tool
- Search tools differ mostly in their seeds.
- Read mappers index the reference once, then stream reads through it.
- For multiple alignment, Clustal Omega over CLUSTALW, unless older work must be reproduced.
Hold loosely
Defaults change between versions, and every speed figure is the developers’ own, from 1990 to 2013.
Seven sequence aligners · sources read 17 October 202615 / 15