Tratopedia
繁中
Settings

Text size

Language

Theme

High contrast

Version

v1.230.2

The release this page was built from. It is what the service worker caches under.

Slide deck

Back

Seven 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.

  1. Sequence alignment · sources read 17 October 2026

    Sequence aligners explained

    LAST · CLUSTALW · Clustal Omega · BWA-MEM · Bowtie2 · BLASTN · BLAT

    Alignment strategies compared1 / 15

  2. 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

  3. Basics

    Alignment in one picture

    Query ACGTTGCAAT against reference ACCTTGCGAT: 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

  4. 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.

    1. 1SeedFind a short exact match through an index
    2. 2ChainGroup seeds that line up
    3. 3ExtendGrow each seed with dynamic programming
    4. 4ScoreKeep alignments that score high enough

    Seven sequence aligners · sources read 17 October 20264 / 15

  5. Seeds

    Seeds at a glance

    Longer seeds run faster but miss weak matches; shorter seeds catch more and cost more time.

    ToolSeedIndex
    BLASTNExact words: 28 bases (megablast, default), 11 (blastn)Query word table
    BLATTwo perfect 11-mers on one diagonalGenome 11-mers in memory
    LASTAdaptive: grown until rareSuffix array
    BWA-MEMSupermaximal exact matches, at least 19 basesFM index
    Bowtie2Fixed, 22 bases (20 in local mode)FM index

    Seven sequence aligners · sources read 17 October 20265 / 15

  6. Search · 1 of 3

    BLASTN

    Fixed word seeds, X-drop extension, and an E-value for every hit

    1. 1Cut the query into words28 bases (megablast) or 11 (blastn)
      queryGATCCTAGGCTTACGATCCTAGGCT1ATCCTAGGCTT2TCCTAGGCTTA3CCTAGGCTTAC4

      14 bases give 14 − 11 + 1 = 4 words of 11, each filed in the lookup table under its query position (blastn task).

    2. 2Extend each hitUngapped X-drop, then gapped
      queryGATCCTAGGCTTACGATGCAsubjectGATCCTAGGCTCACGTCCAG

      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.

    3. 3Score and rankKarlin–Altschul statistics give E-values
      HitMatch / mismatchScore
      A14 / 125
      B13 / 123
      C11 / 022

      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.

    FactValue
    IndexQuery word lookup table
    SeedsExact words of 11 or 28 bases; 7 for short queries
    ConfidenceE-value and bit score
    Best forDivergent DNA, with statistics

    Seven sequence aligners · sources read 17 October 20266 / 15

  7. Search · 2 of 3

    BLAT

    Index the genome, scan the query: fast placement of near-identical sequence

    1. 1Index the genomeNon-overlapping 11-mers held in memory
      genomeTGGACCTAGCAATCGGTACCATTGGACCTAGCA1ATCGGTACCAT12

      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.

    2. 2Require two hitsTwo perfect 11-mers on one diagonal
      CTGGACCTAGCAATCGGTACCATGTGGACCTAGCA−1ATCGGTACCAT−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.

    3. 3Stitch the blocksExons joined into gene-level alignments, splice sites adjusted
      genomeATGCCAGTAAGCAGGTTCGAmRNAATGCCA--------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.

    FactValue
    IndexGenome 11-mers in memory (about 1 GB)
    SeedsTwo perfect 11-mer hits
    ConfidenceScore and identity; no E-value in the default output
    Best formRNA on a genome at 95%+; UCSC pages quote a minimum of 25 or 40 bases

    Seven sequence aligners · sources read 17 October 20267 / 15

  8. Search · 3 of 3

    LAST

    Adaptive seeds, for repeat-rich genomes and whole-genome comparison

    1. 1Build a suffix arraylastdb indexes the reference once
      ACG5ACGTACG1CG6CGTACG2G7GTACG3TACG4

      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.

    2. 2Grow adaptive seedsEach seed lengthens until it is rare in the reference
      queryACGTTCA
      LengthSeedOccurs
      1A2
      2AC2
      3ACG2
      4ACGT1

      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.

    3. 3Extend, then learnGapless then gapped X-drop; last-train learns rates from the data
      ref.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.

    FactValue
    IndexSuffix array (lastdb)
    SeedsAdaptive, grown until rare
    ConfidenceE-value and EG (expected hits per billion query letters)
    Best forRepeat-rich or divergent genomes

    Seven sequence aligners · sources read 17 October 20268 / 15

  9. Map reads · 1 of 2

    BWA-MEM

    Maximal exact matches as seeds; local or end-to-end chosen automatically

    1. 1Find maximal exact matchesSMEMs of at least 19 bases; long ones re-seeded
      ref.ACGTTAGCCATGGACTTGCAATreadACGTTAGCCATGGACTTGCAGTACGTTAGCCATGGACTTGCA20AG2GT2

      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.

    2. 2Chain and extendBanded affine-gap dynamic programming with Z-drop
      SeedReadRef.Length
      A1–20101–12020
      B22–45121–14424
      C27–455001–501919

      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.

    3. 3Pair and reportMates rescued within the insert-size range; MAPQ output
      WindowBases
      μ ± 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.

    FactValue
    IndexFM index (bwa index)
    SeedsSMEMs, at least 19 bases
    ConfidenceMapping quality (MAPQ)
    Best forReads or contigs from 70 bases to megabases

    Seven sequence aligners · sources read 17 October 20269 / 15

  10. Map reads · 2 of 2

    Bowtie2

    Several fixed-length seeds, then SIMD-accelerated extension

    1. 1Pick seeds from the read22 bases (20 in local mode), from the read and its reverse complement
      readTTGCATCCTAAGTCTAGCTTGATTGCATCCTA1CCTAAGTCTA7TCTAGCTTGA13

      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.

    2. 2Look them upThe FM index finds exact, ungapped hits
      ref.TTGCATCCGAAGTCTAGCTTGATTGCATCCTA0CCTAAGTCTA0TCTAGCTTGA1

      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.

    3. 3Extend with SIMDPrioritised hits get SIMD-accelerated dynamic programming
      ModeScoreMinimum
      End-to-end−17−30.6
      Local8151.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.

    FactValue
    IndexFM index (about 3.2 GB for the human genome)
    SeedsFixed, 20–22 bases, no mismatches
    ConfidenceMapping quality (MAPQ)
    Best forReads of about 50 to a few hundred bases

    Seven sequence aligners · sources read 17 October 202610 / 15

  11. Align many · 1 of 2

    CLUSTALW

    The classic progressive multiple alignment

    1. 1Measure distancesEvery pair aligned, by k-tuples or full alignment
      AGATTACAGCABGATTACTGCACGACTTCAGGADGACTTCTGGT
      ABC
      B0.1
      C0.30.4
      D0.50.40.2

      Distance is 1 − identity: A and B differ at 1 of 10 positions, so 0.1.

    2. 2Build a guide treeNeighbour-Joining orders the sequences
      ABCD

      Neighbour-Joining on those distances pairs A with B and C with D; the root goes at the mid-point of the longest path.

    3. 3Align along the treeWeighted profiles, position-specific gap penalties
      AGATTACAGCA1BGATTACTGCA1CGACTTCAGGA2DGACTTCTGGT2

      N match

      Joined in the tree’s order: 1 A with B, 2 C with D, then 3 the two profiles with each other.

    FactValue
    IndexNone (all-pairs distances)
    SeedsNone (a distance tree instead)
    ConfidenceNone
    Best forSmall sets, teaching, reproducing older work

    Seven sequence aligners · sources read 17 October 202611 / 15

  12. Align many · 2 of 2

    Clustal Omega

    Scalable multiple alignment, profile HMM against profile HMM

    1. 1Embed the sequencesmBed: distances to about log N reference sequences
      S1GATTCAGC0, 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.

    2. 2Cluster into a treeK-means or UPGMA, O(N log N)
      S1S2S3S4S5S6

      UPGMA on those vectors puts S1–S3 in one group and S4–S6 in the other.

    3. 3Align HMM to HMMHHalign at each node; iteration optional
      S1GATTCAGCS2GATTCTGCS3GACTCAGCS4GTCT-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.

    FactValue
    IndexNone (mBed vectors)
    SeedsNone (a clustered tree instead)
    ConfidenceNone
    Best forSmall to very large sets; over 190,000 sequences in its authors’ test

    Seven sequence aligners · sources read 17 October 202612 / 15

  13. Side by side

    Seven tools, side by side

    MAPQ is a mapping-quality score, not an E-value.

    ToolJobIndexSeedConfidence
    BLASTNSearchQuery word tableExact word, 11 or 28E-value
    BLATSearchGenome 11-mers in memoryTwo 11-mersScore, identity
    LASTSearchSuffix arrayAdaptiveE-value, EG
    BWA-MEMMap readsFM indexSMEM, 19+MAPQ
    Bowtie2Map readsFM indexFixed, 20–22MAPQ
    CLUSTALWAlign manyNoneNoneNone
    Clustal OmegaAlign manyNoneNoneNone

    Seven sequence aligners · sources read 17 October 202613 / 15

  14. Choosing

    Which one should I use?

    Readings from the comparison, not rankings.

    Your situationSuggested tool
    Short reads, about 50 to a few hundred basesBWA-MEM / Bowtie2
    Long reads or assembled contigsBWA-MEM, or LAST with last-train
    mRNA on its own genome at 95%+ identityBLAT
    Divergent homologues that need E-valuesBLASTN
    Whole genomes with many repeatsLAST
    Multiple alignment of many sequencesClustal Omega

    Seven sequence aligners · sources read 17 October 202614 / 15

  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