Sequence Alignment Algorithms Explained: Global, Local, and BLAST

Quick answer: Sequence alignment is the act of placing two sequences side by side in the arrangement that best supports a claim about their relationship. Two classic algorithms compute that arrangement exactly — Needleman-Wunsch when your claim spans both sequences end to end (global), and Smith-Waterman when your claim concerns a shared region inside longer sequences (local). BLAST is not one of these exact algorithms; it is a heuristic built around them, and knowing the difference tells you when each approach is the right tool.

The theory layer underneath three guides already on this blog: what BLAST is, choosing the right BLAST program, and how to interpret BLAST results. Here we explain the algorithmic machinery those articles assume you know.

What an alignment is really computing

An algorithm cannot rank arrangements without a scoring scheme first. Every pairwise alignment method shares the same three ingredients:

• Match — reward two positions that agree (often 1 or 2).
• Mismatch — penalize two positions that disagree (often -1 or 0).
• Gap — penalize insertions and deletions, usually two pieces: a cost to open a gap and a smaller cost to extend it.

The interesting part of the field is what the scoring encodes biologically: penalizing gap opening heavily says a single long insertion is more plausible than many tiny ones, which is what biology usually supports.

Dynamic programming: Needleman-Wunsch and Smith-Waterman

Both algorithms fill a two-dimensional grid: one axis for sequence A, one for sequence B. Each cell stores the best score of aligning a prefix of A against a prefix of B. Filling the grid down and across, each cell takes the best of three moves: diagonal (the two bases align), down (gap in A), or right (gap in B). When the grid is full, the path traced back from the bottom-right corner is the optimal alignment, and this is why the method is called dynamic programming: an optimal arrangement of the whole pair must contain optimal arrangements of its subprefixes, so the amortized work per cell is constant and the total cost is the product of the sequence lengths.

One tool, two hooks into the same recurrence:

• Needleman-Wunsch (1970) computes the best end-to-end alignment: whole A against whole B. Choose it when the result becomes a reference alignment of two full-length homologs or when your claim is direct relatedness across the length of both sequences.
• Smith-Waterman (1981) finds the best alignment contained somewhere inside the two sequences: a shared domain inside two otherwise unrelated proteins, a conserved element inside two otherwise diverged genomes. It is local because it never requires the path to reach the edges of the grid — it is allowed to start anywhere and drop negative suffixes.

A compact way to remember the pair: global means the alignment must consume everything; local means it may not. That single yes-or-no difference in the recurrence produces the two best-known algorithms in bioinformatics, both running in on the order of the product of lengths, whether scored per-cell as bytes or with a GPU-accelerated kernel.

Why BLAST looks different: seeding and extension

Dynamic programming is exact but expensive: aligning one 2,000-base query against a database of billions of bases is what this article calls out-by-scale impossible. BLAST’s trick is to avoid the exhaustive part wherever it can:

• Seed: break the query into short words (k-mers). A database sequence that resembles the query almost certainly contains at least one identical or near-identical word, so the words act as candidate meeting points.
• Extend: from a hit word, extend and score that region with a limited dynamic-programming pass rather than consulting each pair of positions.
• Score with statistics: convert the extended alignment into a bit score and an E-value that take database size into account, which is what the results table reports (covered fully in the BLAST results interpretation guide).

The cost is honesty about coverage: a seeding-based search is probably complete for your question rather than provably complete. In practice — and this is why BLAST is standard — for real biological questions at sensible parameters the misses it can make are rare.

Indexes on the read side: BWA, Bowtie, minimap2

The Next-Generation Sequencing era (covered in the NGS workflow overview) changed the arithmetic by giving you millions of reads per run. Realigning every one of them with BLAST-style extension against a genome is what matching this volume requires instead:

• FM-index shortcuts. BWA and Bowtie build an index of the reference so read alignment searches directly where the read matches without ever laying out a full grid.
• Long-read tools. minimap2 uses a different seeding scheme geared to long Noisy reads, because a long error-prone read resists short exact seeds.

The right mental model for modern tool names: exact-algorithm machinery rides inside almost every short-read aligner, while the faster public interfaces trade a guaranteed optimum for speed that is correct in almost all cases — and every serious pipeline aligns more reads than bases because it can afford a heuristic that misses the occasional region.

Which kind of alignment solves which job

Common failure modes

• Assuming BLAST reports the exact best alignment. It reports a biologically reliable set of hits obtained by seeding; a rigorous pairwise case may need a true global or local alignment run.
• Ignoring that the score is a claim, not proof. A high score supports a homology claim subject to your scoring scheme; scoring schemes differ across matrices, and a domain may look weak under one and firm under another.
• Treating percent identity and bit score as interchangeable. Bit score normalizes across databases; percent identity can be 100% over two aligned residues and tell you nothing more than that length.
• Using a global method where local is the claim. A homologous domain inside unrelated flanking sequence has no reason to align end to end, so forcing a global alignment destroys the signal you wanted.
• Reusing aligner defaults across entirely different read types. Short-read aligners and long-read mappers use different spacing and error models; the defaults each one ships with are tuned to the read type they were built for.

Key takeaways

• Alignment = a scoring scheme plus the best arrangement consistent with it; without a scoring scheme, an alignment means nothing.
• Needleman-Wunsch is global, whole sequence to whole sequence, exactly computed in the product of lengths; Smith-Waterman is local, allowed to start and stop anywhere in the pair.
• BLAST is a heuristic layered on these ideas: short-word seeding, then measured extension, then statistical scores that scale with database size.
• Modern aligners (BWA, Bowtie, minimap2) trade exhaustive optimality for FM-index and seeding speeds that cover almost every real NGS question.
• Ranking by what the claim is — full homolog, shared domain, big database, millions of reads — is what picks the algorithm, not habit or tool popularity.

Challenge

Write a 10-line Needleman-Wunsch on paper with match 1, mismatch -1, gap -2 and align two 6-character sequences by hand. Then pick a published protein sequence, find its best BLAST hit, and note where the seeded heuristic hit lands and what the coverage of the alignment is. The grid exercise makes the machine feel like yours; the BLAST exercise makes it feel like there is ever more than one sensible alignment per pair.

Related: Aligners exist largely so that mismatches can be counted against a reference — see the step that does the counting in our variant calling guide.

Need help with alignment and sequence analysis in a course or research project? Ampersand Academy offers one-to-one mentoring in bioinformatics and analysis — part of Mahadhi, a development and digital marketing company.

FAQ