Smith-Waterman and Needleman-Wunsch in C and C++: Local and Global Sequence Alignment With Affine Gaps

Why one DNA pair scores 4 aligned end to end and 13 aligned locally, and how to build both alignments, with affine gaps, in tested C and C++ code.

Two rows of shapes with a green band around the aligned stretch, where matching shapes are joined by bars, one pair differs, and one slot is an empty gap, illustrating a local sequence alignment

Align TGTTACGG with GGTTGACTA from end to end, scoring +3 for a match, −3 for a mismatch and −2 for each gap position, and the best possible score is 4. Ask instead for the best-matching stretch of the two and the score is 13, for GTT-AC over GTTGAC. The difference comes from two rules: no cell of the table may fall below zero, and the answer is read from the highest cell instead of the corner. Those two rules are what turn the Needleman-Wunsch algorithm into the Smith-Waterman algorithm.

This guide explains global and local alignment, how substitution tables and affine gap costs score an alignment, and how Gotoh’s three-table method fills and reads back the optimal alignment, with working code in C and C++. It also includes a command-line aligner for FASTA files, a score-only version in linear memory, three mistakes that break alignment programs, and measured speed and memory up to 4,000 letters. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64), and again under WSL and with MSVC on Windows: C with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, C++ with g++ 13.3 and clang++ 18.1.3 under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic -Werror and no warnings. The aligner’s tests run clean under AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind, its scores match Biopython’s on 600 of 600 alignments, and every output block is captured verbatim. The code is in two GitHub repositories whose workflows repeat these checks on each commit.

What Is Pairwise Sequence Alignment?

Pairwise sequence alignment arranges two DNA, RNA or protein sequences in columns so that similar letters line up, inserting gaps where one sequence has letters the other lacks. Each column is scored, and the optimal alignment is the one with the highest total. Global alignment (Needleman-Wunsch) covers both sequences completely; local alignment (Smith-Waterman) finds the highest-scoring pair of segments.

An alignment of GATTACA and GATCA might look like this, with - marking a gap:

GATTACA
|||  ||
GAT--CA

Every column is one of three things: a pair of letters, a letter of the top sequence against a gap, or a letter of the bottom sequence against a gap. A column with two gaps is never useful and is not allowed. The score adds up the columns, so the alignment problem is a search for the best way to place the gaps. Both algorithms solve it exactly by dynamic programming, in O(n·m) time for sequences of lengths n and m.

The two classic algorithms differ in what they are asked to align:

AspectNeedleman-Wunsch (global)Smith-Waterman (local)
AlignsBoth sequences from first letter to lastThe best-scoring segment of each
Published1970, Journal of Molecular Biology1981, Journal of Molecular Biology
Cell ruleBest of diagonal, above and leftThe same, but never below 0
First row and columnRuns of gaps, increasingly negativeAll 0
Answer read fromThe bottom-right cellThe highest cell anywhere
Walk back stops atThe top-left cornerThe first cell that is 0
Typical useTwo sequences known to be related along their lengthFinding a shared domain or motif inside longer sequences

The founding papers are Needleman and Wunsch (1970) and Smith and Waterman (1981). The longest common subsequence is the simplest special case: global alignment with +1 for a match, no mismatches allowed, and free gaps.

Scoring an Alignment: Substitution Tables and Gap Costs

An alignment’s score has two parts: what each pair of letters is worth, and what each gap costs.

Pairs of letters are scored from a substitution table. For DNA a simple table is common, such as +3 for a match and −3 for a mismatch. For proteins, some substitutions are far more likely than others, because amino acids with similar chemistry replace each other in related proteins. The BLOSUM tables of Henikoff and Henikoff (1992) score each pair from substitutions observed in conserved blocks of related proteins. BLOSUM62, built from blocks clustered at 62% identity, is the usual default for protein searches. In it, tryptophan against itself (W/W) scores 11, alanine against itself 4, and W against A −3.

Gaps can be charged in two ways:

  • Linear gap costs charge the same for every gap position: a gap of k letters costs k·d. Three separate one-letter gaps cost the same as one gap of three.
  • Affine gap costs charge a larger amount to open a gap and a smaller amount to extend it. Here a gap of k letters costs open + k × extend, the form w = uk + v used by Gotoh in 1982. One insertion or deletion of three letters is a single event in evolution, so it should cost less than three scattered ones.

The difference shows up in the alignments, not just the scores. With linear gaps, these two DNA sequences align with three scattered one-letter gaps; with a gap costing 8 + k, the same letters prefer one gap of three (the last two blocks of the C program’s output, shown in full further down):

Global, DNA, linear gaps
GAAAAAGATAGAGC
|||||||| | | |
GAAAAAGA-A-A-C
score 27

Global, DNA, affine gaps
GAAAAAGATAGAGC
||||||||   | |
GAAAAAGA---AAC
score 16

Under the affine costs, the first alignment would score only 6: its three gaps cost 9 each, 27 in all, while the second pays 11 for one gap of three and 3 for a mismatch. The aligner finds the second, with a score of 16.

Two conventions for the same two numbers

Not every tool means the same thing by “gap open” and “gap extend”. This article, Gotoh’s paper and the code below charge open once plus extend for every position. EMBOSS needle and Biopython’s PairwiseAligner charge open for the first position and extend for each further one: the EMBOSS needle documentation gives the penalty for a gap of n positions as “gap opening penalty + (n – 1) * gap extension penalty”, with defaults of 10.0 and 0.5.

Gap costs given asGap of 1Gap of 3Equivalent setting in the other convention
open 10, extend 0.5, charged as open + (n − 1) × extend (EMBOSS, Biopython)1011open 9.5, extend 0.5 here
open 10, extend 0.5, charged as open + n × extend (this article, Gotoh)10.511.5open 10.5, extend 0.5 in EMBOSS

The conversion is a single subtraction, and skipping it is easy to miss because both settings produce plausible alignments. The cross-check against Biopython later in this article shows how much it matters: with the costs converted, the scores agree on 600 of 600 alignments; passed across unchanged, on 83 of 600.

The Recurrences: Needleman-Wunsch, Smith-Waterman and Gotoh

Write s(x, y) for the table score of a pair of letters and, for linear gaps, d for the cost of one gap position. Let F(i, j) be the best score for aligning the first i letters of the first sequence with the first j letters of the second. The last column of that alignment is a pair, a letter of the first sequence over a gap, or a letter of the second over a gap, so:

Needleman-Wunsch (global)
F(0, 0) = 0,   F(i, 0) = -i·d,   F(0, j) = -j·d
F(i, j) = max( F(i-1, j-1) + s(a[i], b[j]),
               F(i-1, j)   - d,
               F(i, j-1)   - d )
answer:  F(n, m)

Smith-Waterman (local)
H(i, 0) = H(0, j) = 0
H(i, j) = max( 0,
               H(i-1, j-1) + s(a[i], b[j]),
               H(i-1, j)   - d,
               H(i, j-1)   - d )
answer:  the largest H(i, j) anywhere in the table

The 0 in the Smith-Waterman rule means “start a new alignment here”: whenever every way of reaching a cell has a negative total, it is better to drop the prefix and start fresh. That is why the first row and column are 0 and why the answer can sit anywhere in the table.

Affine gaps need more than one number per cell. Whether the next gap position costs open + extend or just extend depends on whether the alignment already ends in a gap, and a single F(i, j) does not remember that. Gotoh’s 1982 method keeps three tables, one for each way an alignment can end:

M(i, j) = s(a[i], b[j]) + max( M(i-1, j-1), X(i-1, j-1), Y(i-1, j-1) )      ends in a pair
X(i, j) = max( M(i-1, j) - open - extend,                                    ends in a[i] over a gap
               X(i-1, j) - extend,
               Y(i-1, j) - open - extend )
Y(i, j) = max( M(i, j-1) - open - extend,                                    ends in b[j] over a gap
               Y(i, j-1) - extend,
               X(i, j-1) - open - extend )

Moving from M into X or Y opens a gap; staying in X or Y extends it. The global score is the largest of the three at (n, m). For local alignment, the max inside M also includes 0, and the answer is the largest M anywhere: a local alignment never needs to end in a gap, because removing a trailing gap can only raise the score. The work is still one pass over an (n + 1) × (m + 1) grid, three times the arithmetic of the linear version.

Filling the Smith-Waterman Table

The table below is the Smith-Waterman table for the two sequences from the opening, with linear gaps (with open = 0, the three tables collapse into one, the best of M, X and Y). Rows follow TGTTACGG and columns GGTTGACTA. The first row and column are 0, and so is every cell where all three ways in would be negative.

Smith-Waterman table for TGTTACGG and GGTTGACTA Match +3, mismatch −3, each gap position −2; no cell goes below 0 G G T T G A C T A T G T T A C G G 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 1 0 0 3 1 0 3 3 1 1 6 4 2 1 0 0 1 1 6 4 4 3 1 5 3 0 0 0 4 9 7 5 3 4 2 0 0 0 2 7 6 10 8 6 7 0 0 0 0 5 4 8 13 11 9 0 3 3 1 3 8 6 11 10 8 0 3 6 4 2 6 5 9 8 7 The alignment ends at the highest cell (13) and the walk back stops at the first 0. GTT-AC over GTTGAC, score 13
Figure 1: The Smith-Waterman table for TGTTACGG and GGTTGACTA. The best local alignment ends at the highest cell, 13, and the walk back through the outlined cells stops at the first 0.

The highest cell is 13, at the C in row 6 and column 7. Walking back from it:

  1. 13 = 10 + 3: C over C, a match, from the diagonal.
  2. 10 = 7 + 3: A over A, from the diagonal.
  3. 7 = 9 − 2: a gap in the first sequence against the G in column 5, from the cell to the left.
  4. 9, 6 and 3, each 3 more than the diagonal before it: T over T, T over T, G over G.
  5. The next diagonal cell is 0, so the alignment starts at the G/G pair.

Read forwards, the walk gives GTT-AC over GTTGAC with a score of 13: five matches (15) and one gap position (−2). The C program prints exactly this alignment and reports that it covers letters 2–6 of the first sequence and 2–7 of the second.

Sequence Alignment in C

The C version is a small library, align.c, with three functions: align_global and align_local return one optimal alignment, and align_score returns only the score, in linear memory. The interface describes the scoring and the result:

/* How an alignment is scored. A gap of length k costs
 * gap_open + k * gap_extend, so gap_open = 0 gives linear gap costs. */
typedef struct {
    const char *letters;  /* the alphabet, e.g. "ACGT"; lowercase input matches too */
    const int *table;     /* score of letters[i] against letters[j] at [i * n + j] */
    int gap_open;         /* charged once per gap, 0 or more */
    int gap_extend;       /* charged for every position of a gap, 1 or more */
} Scoring;

/* One optimal alignment. top and bottom have the same length and use '-'
 * for a gap. The aligned part of s1 is s1[start1, end1), of s2 s2[start2, end2);
 * a global alignment always covers both sequences completely. */
typedef struct {
    char *top;
    char *bottom;
    int score;
    size_t start1, end1;
    size_t start2, end2;
} Alignment;

The alphabet is a string such as "ACGT" or the 24 BLOSUM letters, and the table is a flat array indexed by the two letters’ positions in it. A gap of length k costs gap_open + k * gap_extend, so gap_open = 0 gives linear gaps. Letters are looked up through an array of 256 entries indexed by unsigned char, which matters for one of the mistakes later: any byte, including lowercase letters and bytes above 127, has a defined entry, and a letter that is not in the alphabet is reported as an error instead of being scored as something else.

Filling Gotoh’s three tables

fill applies the recurrences from the previous section to every cell. The two flags that differ between global and local alignment are the edges and the zero floor:

static int fill(Tables *t, const unsigned char *a, const unsigned char *b,
                const Scoring *sc, size_t width, int local)
{
    size_t n = t->n, m = t->m, cells;
    t->cols = m + 1;
    if (t->cols > SIZE_MAX / (n + 1) || (n + 1) * t->cols > SIZE_MAX / sizeof(int))
        return ALIGN_NO_MEMORY;
    cells = (n + 1) * t->cols;
    t->M = malloc(cells * sizeof(int));
    t->X = malloc(cells * sizeof(int));
    t->Y = malloc(cells * sizeof(int));
    if (t->M == NULL || t->X == NULL || t->Y == NULL)
        return ALIGN_NO_MEMORY;

    const int open = sc->gap_open + sc->gap_extend, ext = sc->gap_extend;
    for (size_t i = 0; i <= n; i++) {
        for (size_t j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                /* Global: only the corner is a real start, and the edges are
                 * one gap. Local: an alignment may start anywhere. */
                AT(t->M, i, j) = (local || (i == 0 && j == 0)) ? 0 : NEG;
                AT(t->X, i, j) = (!local && j == 0 && i > 0) ? -(sc->gap_open + (int)i * ext) : NEG;
                AT(t->Y, i, j) = (!local && i == 0 && j > 0) ? -(sc->gap_open + (int)j * ext) : NEG;
                continue;
            }
            int diag = max3(AT(t->M, i - 1, j - 1), AT(t->X, i - 1, j - 1), AT(t->Y, i - 1, j - 1));
            if (local && diag < 0)
                diag = 0;                  /* start a new local alignment here */
            AT(t->M, i, j) = sc->table[a[i - 1] * width + b[j - 1]] + diag;
            AT(t->X, i, j) = max3(AT(t->M, i - 1, j) - open, AT(t->X, i - 1, j) - ext,
                                  AT(t->Y, i - 1, j) - open);
            AT(t->Y, i, j) = max3(AT(t->M, i, j - 1) - open, AT(t->Y, i, j - 1) - ext,
                                  AT(t->X, i, j - 1) - open);
        }
    }
    return ALIGN_OK;
}

NEG is INT_MIN / 4, a “minus infinity” for cells no alignment can reach, chosen so that subtracting a gap cost cannot overflow. Before filling, the library also checks that no possible score can overflow an int: an alignment has at most n + m columns, and none can change the score by more than the largest table entry or gap cost, so sequences long enough to break that bound are rejected with ALIGN_TOO_LONG.

Walking back to the alignment

trace starts at the cell where the alignment ends and, at each step, works out which of the three tables the current value came from. It writes the columns backwards, then reverses them:

/* Walks back from (i, j) in the given state and writes the alignment. */
static int trace(const Tables *t, const char *s1, const char *s2,
                 const unsigned char *a, const unsigned char *b,
                 const Scoring *sc, size_t width, int local,
                 size_t i, size_t j, int state, Alignment *out)
{
    const int open = sc->gap_open + sc->gap_extend, ext = sc->gap_extend;
    size_t cap = i + j, len = 0;
    char *top = malloc(cap + 1), *bottom = malloc(cap + 1);
    if (top == NULL || bottom == NULL) {
        free(top);
        free(bottom);
        return ALIGN_NO_MEMORY;
    }
    out->end1 = i;
    out->end2 = j;
    while (i > 0 || j > 0) {
        if (state == STATE_M) {
            int v = AT(t->M, i, j) - sc->table[a[i - 1] * width + b[j - 1]];
            top[len] = s1[i - 1];
            bottom[len++] = s2[j - 1];
            i--, j--;
            if (local && v == 0)
                break;                     /* the alignment starts at this pair */
            state = v == AT(t->M, i, j) ? STATE_M : v == AT(t->X, i, j) ? STATE_X : STATE_Y;
        } else if (state == STATE_X) {
            int v = AT(t->X, i, j);
            top[len] = s1[i - 1];
            bottom[len++] = '-';
            i--;
            state = v == AT(t->M, i, j) - open ? STATE_M
                  : v == AT(t->X, i, j) - ext  ? STATE_X : STATE_Y;
        } else {
            int v = AT(t->Y, i, j);
            top[len] = '-';
            bottom[len++] = s2[j - 1];
            j--;
            state = v == AT(t->M, i, j) - open ? STATE_M
                  : v == AT(t->Y, i, j) - ext  ? STATE_Y : STATE_X;
        }
    }
    out->start1 = i;
    out->start2 = j;
    for (size_t k = 0; k < len / 2; k++) {    /* the walk ran backwards */
        char c = top[k];
        top[k] = top[len - 1 - k];
        top[len - 1 - k] = c;
        c = bottom[k];
        bottom[k] = bottom[len - 1 - k];
        bottom[len - 1 - k] = c;
    }
    top[len] = bottom[len] = '\0';
    out->top = top;
    out->bottom = bottom;
    return ALIGN_OK;
}

Recomputing the predecessor from the stored values, instead of storing a direction for each cell, keeps the memory at three tables of int and is exact because all scores are integers. Where two predecessors give the same value, the order of the tests decides which optimal alignment is returned. For a local alignment, the walk stops at the pair whose diagonal value was 0: that is where the alignment started.

The complete example

The demo aligns the article’s three pairs of sequences: the DNA pair from the opening, the protein pair HEAGAWGHEE and PAWHEAE with BLOSUM50 and a linear gap cost of 8 (the worked example in chapter 2 of Durbin, Eddy, Krogh and Mitchison’s Biological Sequence Analysis), and the affine-gap pair.

/* align_demo.c - global and local alignments of the article's examples. */
#include <stdio.h>

#include "align.h"
#include "blosum.h"

/* +3 for a match, -3 for a mismatch; rows and columns in the order ACGT */
static const int DNA[4 * 4] = {
     3, -3, -3, -3,
    -3,  3, -3, -3,
    -3, -3,  3, -3,
    -3, -3, -3,  3,
};

static int show(const char *title, const char *s1, const char *s2,
                const Scoring *sc, int local)
{
    Alignment al;
    int err = local ? align_local(s1, s2, sc, &al) : align_global(s1, s2, sc, &al);
    if (err != ALIGN_OK) {
        fprintf(stderr, "%s: %s\n", title, align_error(err));
        return 1;
    }
    printf("%s\n", title);
    alignment_print(&al, sc, stdout);
    printf("score %d", al.score);
    if (local)
        printf(", letters %zu-%zu of the first and %zu-%zu of the second",
               al.start1 + 1, al.end1, al.start2 + 1, al.end2);
    printf("\n\n");
    alignment_free(&al);
    return 0;
}

int main(void)
{
    const Scoring dna_linear = {"ACGT", DNA, 0, 2};            /* every gap position costs 2 */
    const Scoring dna_affine = {"ACGT", DNA, 8, 1};            /* a gap of k costs 8 + k */
    const Scoring blosum50 = {BLOSUM_LETTERS, BLOSUM50, 0, 8}; /* every gap position costs 8 */
    int failed = 0;

    failed |= show("Local, DNA, linear gaps", "TGTTACGG", "GGTTGACTA", &dna_linear, 1);
    failed |= show("Global, DNA, linear gaps", "TGTTACGG", "GGTTGACTA", &dna_linear, 0);
    failed |= show("Global, BLOSUM50, linear gaps", "HEAGAWGHEE", "PAWHEAE", &blosum50, 0);
    failed |= show("Local, BLOSUM50, linear gaps", "HEAGAWGHEE", "PAWHEAE", &blosum50, 1);
    failed |= show("Global, DNA, linear gaps", "GAAAAAGATAGAGC", "GAAAAAGAAAC", &dna_linear, 0);
    failed |= show("Global, DNA, affine gaps", "GAAAAAGATAGAGC", "GAAAAAGAAAC", &dna_affine, 0);
    return failed;
}

Output:

Local, DNA, linear gaps
GTT-AC
||| ||
GTTGAC
score 13, letters 2-6 of the first and 2-7 of the second

Global, DNA, linear gaps
TGTT-ACGG
 ||| ||  
GGTTGACTA
score 4

Global, BLOSUM50, linear gaps
HEAGAWGHE-E
    || || |
--P-AW-HEAE
score 1

Local, BLOSUM50, linear gaps
AWGHE
|| ||
AW-HE
score 28, letters 5-9 of the first and 2-5 of the second

Global, DNA, linear gaps
GAAAAAGATAGAGC
|||||||| | | |
GAAAAAGA-A-A-C
score 27

Global, DNA, affine gaps
GAAAAAGATAGAGC
||||||||   | |
GAAAAAGA---AAC
score 16

The global and local results for the same pair can be very different. Globally, HEAGAWGHEE and PAWHEAE score only 1, because the shorter sequence must be stretched across the whole of the longer one with five gap positions. Locally, the best segment pair is AWGHE over AW-HE, with a score of 28. The | marks identical letters, and in protein alignments + marks a different pair that still scores above 0; there are none in these examples. Several global alignments of HEAGAWGHEE and PAWHEAE score 1, and the program prints one of them.

The Alignment Score in Linear Memory

When only the score is needed, for example to rank many candidate sequences before aligning the best ones, the three full tables are unnecessary. Every cell depends only on the row above and the cell to the left, so align_score keeps two rows of each table, 6 × (m + 1) integers in all:

    /* Two rows of each table: the previous row (pM, pX, pY) and this one. */
    int *pM = row, *pX = pM + m + 1, *pY = pX + m + 1;
    int *cM = pY + m + 1, *cX = cM + m + 1, *cY = cX + m + 1;
    const int open = sc->gap_open + sc->gap_extend, ext = sc->gap_extend;
    int best = 0;
    for (size_t j = 0; j <= m; j++) {
        pM[j] = (local || j == 0) ? 0 : NEG;
        pX[j] = NEG;
        pY[j] = (!local && j > 0) ? -(sc->gap_open + (int)j * ext) : NEG;
    }
    for (size_t i = 1; i <= n; i++) {
        cM[0] = local ? 0 : NEG;
        cX[0] = local ? NEG : -(sc->gap_open + (int)i * ext);
        cY[0] = NEG;
        for (size_t j = 1; j <= m; j++) {
            int diag = max3(pM[j - 1], pX[j - 1], pY[j - 1]);
            if (local && diag < 0)
                diag = 0;
            cM[j] = sc->table[a[i - 1] * ab.size + b[j - 1]] + diag;
            cX[j] = max3(pM[j] - open, pX[j] - ext, pY[j] - open);
            cY[j] = max3(cM[j - 1] - open, cY[j - 1] - ext, cX[j - 1] - open);
            if (cM[j] > best)
                best = cM[j];
        }
        int *tmp;
        tmp = pM, pM = cM, cM = tmp;
        tmp = pX, pX = cX, cX = tmp;
        tmp = pY, pY = cY, cY = tmp;
    }
    *score = local ? best : max3(pM[m], pX[m], pY[m]);

At 4,000 letters this swaps 192 MB of tables for 96 KB of rows. Recovering the alignment itself in linear memory is also possible, by splitting the problem at the middle row and recursing on the two halves, which roughly doubles the work. That is Hirschberg’s method, described in the longest common subsequence article linked above, which Myers and Miller (1988) extended to affine gaps.

A Command-Line Aligner for FASTA Files

seqalign reads the first sequence from each of two FASTA files, skipping header lines that start with > and any whitespace, and prints the alignment:

seqalign [-local] [-matrix BLOSUM62|BLOSUM50|DNA] [-open N] [-extend N] [-score] FILE1 FILE2

The defaults are BLOSUM62 with open 11 and extend 1, a gap of k costing 11 + k; BLASTP reports the same two numbers for BLOSUM62 (“Existence: 11, Extension: 1”). For the DNA example, with the first file split across two lines and partly in lowercase:

$ seqalign -local -matrix DNA -open 0 -extend 2 dna1.fa dna2.fa
GTT-Ac
||| ||
GTTGAC
score 13, letters 2-6 of the first and 2-7 of the second

The aligned rows keep the input’s letters as written, so the lowercase c survives. A letter that is not in the chosen alphabet, such as U in an RNA sequence aligned with the DNA table, stops the program with seqalign: a sequence holds a letter outside the alphabet and exit status 2. The -score option prints only the score and uses align_score.

Sequence Alignment in C++

The C++17 version keeps the same algorithm in one function. A Scoring class owns the letter lookup and the table and throws std::invalid_argument for a letter outside the alphabet, and each cell of the table is a small struct holding M, X and Y together:

Alignment align(std::string_view s1, std::string_view s2, const Scoring& sc, Mode mode)
{
    using detail::Cell;
    using detail::neg;
    const auto a = detail::encode(s1, sc), b = detail::encode(s2, sc);
    const std::size_t n = a.size(), m = b.size();
    sc.check_lengths(n, m);
    const bool local = mode == Mode::local;
    const int open = sc.open() + sc.extend(), ext = sc.extend();

    std::vector<Cell> t((n + 1) * (m + 1));
    auto at = [&](std::size_t i, std::size_t j) -> Cell& { return t[i * (m + 1) + j]; };
    for (std::size_t i = 0; i <= n; ++i) {
        for (std::size_t j = 0; j <= m; ++j) {
            Cell& c = at(i, j);
            if (i == 0 || j == 0) {
                c.m = (local || (i == 0 && j == 0)) ? 0 : neg;
                c.x = (!local && j == 0 && i > 0) ? -(sc.open() + static_cast<int>(i) * ext) : neg;
                c.y = (!local && i == 0 && j > 0) ? -(sc.open() + static_cast<int>(j) * ext) : neg;
                continue;
            }
            const Cell& d = at(i - 1, j - 1);
            const Cell& up = at(i - 1, j);
            const Cell& left = at(i, j - 1);
            int diag = std::max({d.m, d.x, d.y});
            if (local && diag < 0)
                diag = 0;                      // start a new local alignment here
            c.m = sc.score(a[i - 1], b[j - 1]) + diag;
            c.x = std::max({up.m - open, up.x - ext, up.y - open});
            c.y = std::max({left.m - open, left.y - ext, left.x - open});
        }
    }

    // Where the walk back starts: the best M cell for a local alignment
    // (or nowhere, if nothing scores above 0), the corner for a global one.
    Alignment al;
    std::size_t i = n, j = m;
    char state = 'm';
    if (local) {
        i = j = 0;
        for (std::size_t r = 1; r <= n; ++r)
            for (std::size_t c = 1; c <= m; ++c)
                if (at(r, c).m > al.score) {
                    al.score = at(r, c).m;
                    i = r;
                    j = c;
                }
    } else {
        const Cell& c = at(n, m);
        al.score = std::max({c.m, c.x, c.y});
        state = al.score == c.m ? 'm' : al.score == c.x ? 'x' : 'y';
    }
    al.end1 = i;
    al.end2 = j;
    while (i > 0 || j > 0) {
        if (state == 'm') {
            const int v = at(i, j).m - sc.score(a[i - 1], b[j - 1]);
            al.top += s1[--i];
            al.bottom += s2[--j];
            if (local && v == 0)
                break;                         // the alignment starts at this pair
            const Cell& p = at(i, j);
            state = v == p.m ? 'm' : v == p.x ? 'x' : 'y';
        } else if (state == 'x') {
            const int v = at(i, j).x;
            al.top += s1[--i];
            al.bottom += '-';
            const Cell& p = at(i, j);
            state = v == p.m - open ? 'm' : v == p.x - ext ? 'x' : 'y';
        } else {
            const int v = at(i, j).y;
            al.top += '-';
            al.bottom += s2[--j];
            const Cell& p = at(i, j);
            state = v == p.m - open ? 'm' : v == p.y - ext ? 'y' : 'x';
        }
    }
    al.start1 = i;
    al.start2 = j;
    std::reverse(al.top.begin(), al.top.end());       // the walk ran backwards
    std::reverse(al.bottom.begin(), al.bottom.end());
    return al;
}

Storing the three values side by side in one std::vector<Cell> keeps them in the same cache line. The program’s main aligns the same six examples as the C demo, and its output is byte-for-byte identical to the C output above; a test in each repository compares the output with the same expected file. The C++ tests repeat the known results, the brute force and the long-pair checks.

Checking the Aligner Against Brute Force and Biopython

Three checks, each independent of the dynamic program, support the results on this page.

A brute force over every alignment. For short sequences, the test program builds every possible alignment column by column, scores each one directly from the scoring rules, and keeps the best. For local alignment, it repeats that for every pair of substrings. Each random pair gets its own random scoring: a three-letter alphabet, a table of random scores from −5 to 5, and random gap costs. The tables are deliberately not symmetric, so that a program which looks up the two letters in the wrong order cannot pass by accident. Every returned alignment is also checked: removing its gaps must give back the stated parts of the inputs, its columns must add up to its score, and align_score must agree.

random pairs matching the brute force, global and local: 5000 of 5000
protein pairs up to 400 letters where all three functions agree: 200 of 200
0 failed

An independent implementation. Biopython’s PairwiseAligner, which reports that it uses the Gotoh algorithm for these settings, scored 600 alignments of random protein pairs up to 300 letters long with BLOSUM62, half of them related by mutation, across five gap settings:

alignments where seqalign and Biopython agree on the score: 600 of 600
with the gap costs passed to Biopython unchanged: 83 of 600

The second line is the gap convention from earlier, measured: the same numbers given to Biopython without converting them change the score on 517 of the 600 alignments.

Textbook results. The DNA example’s score of 13 and alignment GTT-AC over GTTGAC, and the protein example’s global score of 1 and local alignment AWGHE over AW-HE with score 28, are both checked by the tests.

Three Mistakes That Break an Alignment Program

1. A local alignment without its two rules

Smith-Waterman needs both rules: the zero floor on every cell, and the answer taken from the highest cell. Leaving out either one still produces a number, so the mistake is easy to miss. This program scores the opening example all four ways:

/* local_without_zero.c - what Smith-Waterman scores when one of its two
 * local-alignment rules is left out: the zero floor on every cell, and
 * taking the answer from the best cell instead of the bottom-right corner.
 * Linear gaps, +3 for a match, -3 for a mismatch, -2 per gap position. */
#include <stdio.h>
#include <string.h>

#define MAXLEN 32

static int score(const char *a, const char *b, int floor_at_zero, int best_cell)
{
    int H[MAXLEN + 1][MAXLEN + 1];
    size_t n = strlen(a), m = strlen(b);
    int best = -1000;
    for (size_t i = 0; i <= n; i++)
        for (size_t j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                /* Without the floor, the edges are runs of gaps, as in a
                 * global alignment. */
                H[i][j] = floor_at_zero ? 0 : -2 * (int)(i + j);
                continue;
            }
            int diag = H[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 3 : -3);
            int up = H[i - 1][j] - 2, left = H[i][j - 1] - 2;
            int h = diag > up ? diag : up;
            h = h > left ? h : left;
            if (floor_at_zero && h < 0)
                h = 0;
            H[i][j] = h;
            if (h > best)
                best = h;
        }
    return best_cell ? best : H[n][m];
}

int main(void)
{
    const char *a = "TGTTACGG", *b = "GGTTGACTA";
    printf("zero floor, best cell (Smith-Waterman)   %3d\n", score(a, b, 1, 1));
    printf("zero floor, bottom-right corner          %3d\n", score(a, b, 1, 0));
    printf("no floor, best cell                      %3d\n", score(a, b, 0, 1));
    printf("no floor, bottom-right corner (global)   %3d\n", score(a, b, 0, 0));
    return 0;
}

Output:

zero floor, best cell (Smith-Waterman)    13
zero floor, bottom-right corner            7
no floor, best cell                       10
no floor, bottom-right corner (global)     4

Only the first line is a local alignment score. Without the floor and with the corner as the answer, the program computes a global alignment and reports 4. With the floor but reading the corner, it finds the best alignment that must end at the last letter of both sequences, 7. Without the floor but taking the best cell, it finds the best alignment that must start at the first letter of both, 10. The tests catch all of these with the known score of 13 and with the brute force over substrings.

2. Looking up scores with c - 'A'

Protein tables are often stored with one row per letter of the alphabet and looked up with toupper(c) - 'A'. That works for the letters the table has rows for, and for no others. The table here has entries for A to Y, but Z is a legal protein letter (glutamate or glutamine, used when the two cannot be told apart):

/* letter_index.c - looking up a score with toupper(c) - 'A' in a table
 * that has one entry for each letter from A to Y. Z is a legal protein
 * letter (glutamate or glutamine), and it reads past the end of the table.
 * The entries are BLOSUM62's scores for a letter against itself. */
#include <ctype.h>
#include <stdio.h>

/*                           A  B  C  D  E  F  G  H  I  J  K  L  M */
static const int SELF[25] = {4, 0, 9, 6, 5, 6, 6, 8, 4, 0, 5, 4, 5,
/*                           N  O  P  Q  R  S  T  U  V  W  X  Y */
                             6, 0, 7, 5, 5, 4, 5, 0, 4, 11, 0, 7};

static int self_score(const char *s)
{
    int total = 0;
    for (; *s != '\0'; s++)
        total += SELF[toupper((unsigned char)*s) - 'A'];
    return total;
}

int main(void)
{
    printf("MKTAYIAK  %d\n", self_score("MKTAYIAK"));
    printf("MKTZYIAK  %d\n", self_score("MKTZYIAK"));
    return 0;
}

Compiled with GCC 13.3 at -O2, without sanitizers:

MKTAYIAK  39
MKTZYIAK  990059300

The second sequence has a lower self-score than the first, since Z takes the place of an A, yet the program reports almost a billion: SELF[25] read four bytes from whatever follows the table in memory. The number changes with the compiler and options; at -O0 it was 1096043376. Neither GCC nor Clang warned with -Wall -Wextra. AddressSanitizer stops the program at the bad read (reports on this page are summarized to the error, the access and the source line):

AddressSanitizer: global-buffer-overflow
READ of size 4 at letter_index.c:17 in self_score
0 bytes after global variable 'SELF' (letter_index.c), size 100 bytes

UndefinedBehaviorSanitizer reports it as letter_index.c:17:22: runtime error: index 25 out of bounds for type 'int [25]'. A lowercase letter outside the table and any byte above 127 are just as dangerous: c - 'A' is then negative, or larger than the table. The fix used in align.c is a 256-entry lookup indexed by unsigned char, filled with −1 for every byte that is not in the alphabet, and an error for any −1.

3. Mixing gap-cost conventions

The third mistake leaves no trace in the output: every alignment looks plausible, and only the scores, and sometimes the placement of the gaps, are wrong. As measured above, passing “open 11, extend 1” to a tool that charges the opening cost on the first position instead of on top of it changed the score on 517 of 600 alignments. When comparing results between tools, check which convention each uses and convert: in a tool that charges open + (n − 1) × extend, the equivalent of this article’s open and extend is open + extend and extend.

Checking the tests with deliberate mistakes

A test suite is only as good as the mistakes it notices. tests/mutations.py puts each of ten plausible mistakes into a copy of align.c, builds the tests against it with AddressSanitizer and UndefinedBehaviorSanitizer, and records how they fail. Two further changes pick a different alignment with the same score, and must pass:

mistake                                              result
local cells not floored at zero                      caught: AddressSanitizer: heap-buffer-overflow in trace (align.c:151)
extending a gap charged as opening one               caught: FAILED line 154: global s1="GAAAAAGATAGAGC" s2="GAAAAAGAAAC" open=8 extend=1: score 6, wanted 16
the gap-open cost never charged                      caught: AddressSanitizer: stack-buffer-overflow in trace (align.c:168)
global edge gaps without the opening cost            caught: FAILED line 151: global s1="ACG" s2="" open=8 extend=1: columns add up to -11, reported score -3
the two letters looked up in the wrong order         caught: AddressSanitizer: stack-buffer-overflow in trace (align.c:168)
local answer read from the bottom-right corner       caught: FAILED line 154: local s1="TGTTACGG" s2="GGTTGACTA" open=0 extend=2: score 7, wanted 13
traceback buffer one column short                    caught: AddressSanitizer: heap-buffer-overflow in trace (align.c:184)
top row letter taken one position off                caught: FAILED line 144: local s1="TGTTACGG" s2="GGTTGACTA" open=0 extend=2: top row "TTA-CG" is not s1[1, 6)
local traceback runs past the start                  caught: AddressSanitizer: heap-buffer-overflow in trace (align.c:151)
align_score never swaps its gap rows                 caught: FAILED line 169: align_score global s1="HEAGAWGHEE" s2="PAWHEAE": -17, wanted 1
global traceback prefers a gap to a pair on a tie    passes: still an optimal alignment
a gap in s1 never directly after a gap in s2         passes: still an optimal alignment
mistakes the tests miss: 0

Two results are worth a closer look. Looking up the two letters in the wrong order is only caught because the random tables are not symmetric; with BLOSUM62 or the DNA table, which are, it passes every check. And the last line is an equivalent change, not a bug: forbidding a gap in the first sequence directly after a gap in the second loses nothing, because two adjacent gaps can always be written in the other order for the same score.

How Fast Is Sequence Alignment, and How Much Memory?

How This Was Measured

SettingValue
Date testedNovember 16, 2026
HardwareCloud VM, 2 vCPUs, Intel Xeon @ 2.10 GHz
Operating systemUbuntu 24.04.5 LTS, x86-64
CompilerGCC 13.3.0, CMake Release build (-O3 -DNDEBUG)
InputTwo pseudo-random protein sequences of equal length over the 20 amino acids, from a fixed seed
ScoringBLOSUM62, a gap of k costs 11 + k
What is timedOne call to align_global, align_local (both including the tables, the walk back and all allocations) and align_score
StatisticMedian of 5 runs
CheckThe score-only result must equal the global alignment’s score, or the program exits

All figures come from one machine, single-threaded, with no CPU pinning or frequency-scaling control and no percentiles. The ns/cell column is for align_score.

length  global ms   local ms score-only ms  tables MB  ns/cell
   500        1.0        1.0          1.0        3.0     3.89
  1000        4.3        4.1          3.9       12.0     3.89
  2000       19.7       18.4         15.5       48.0     3.88
  4000       93.1       78.5         63.1      192.1     3.94

Time grows with the number of cells, n × m: each doubling of the length multiplies it by about four, from 15.5 ms at 2,000 letters to 63.1 ms at 4,000 for the score alone. align_score costs a steady 3.9 ns per cell at every length; its six rows, 96 KB at 4,000 letters, fit in the processor’s caches (an inference from the steady cost, not a profile). The full alignment costs more, 93.1 ms at 4,000 letters, and the gap widens with the length: its three tables, 192 MB at 4,000 letters, are written once and read again during the walk back.

Memory is the real limit of the full-table approach. Two sequences of 100,000 letters would need 3 × 10¹⁰ cells, 120 GB of int tables, while the score alone would still need about 2.4 MB. That is why programs that align long sequences use linear-space methods such as Myers and Miller’s, or restrict the table to a band around the diagonal.

For context, Biopython’s PairwiseAligner, whose aligner is written in C, took a median of 68.9 ms to compute the global score of a 4,000-letter pair on the same machine, about the same as align_score‘s 63.1 ms. Production search tools are much faster: SIMD implementations process many cells per instruction, and Farrar’s striped Smith-Waterman (2007) reported 2 to 8 times the speed of earlier SIMD versions. BLAST is faster still because it does not fill the whole table at all: it starts from short exact word matches and extends them, which is a heuristic and can miss alignments that Smith-Waterman finds.

Key Takeaways

  • Global alignment (Needleman-Wunsch) covers both sequences; local alignment (Smith-Waterman) finds the best-scoring pair of segments. The same DNA pair scored 4 globally and 13 locally.
  • Smith-Waterman is two rules on top of Needleman-Wunsch: no cell below 0, and the answer from the highest cell. Dropping either still produced a number: 7 or 10 instead of 13.
  • Affine gaps need three tables, one for each way an alignment can end, and they turn three scattered gaps into one gap of three.
  • “Gap open” means different things in different tools. Unconverted, the same numbers changed Biopython’s score on 517 of 600 alignments.
  • Index scoring tables safely. c - 'A' read past a 25-entry table for the letter Z, without a compiler warning.
  • The score alone needs only two rows of each table, 96 KB instead of 192 MB at 4,000 letters, at a steady 3.9 ns per cell.

Frequently Asked Questions

Conclusion

Global and local alignment are the same dynamic program with different edges and a different place to look for the answer, and affine gaps add only two more numbers per cell. What decides whether an aligner can be trusted is less the recurrence than the details around it: the zero floor and the best cell, a letter lookup that cannot run off the end of the table, scores that cannot overflow, and gap costs that mean what the user thinks they mean.

Those details are also why the checks matter more than the code. A brute force over every alignment, asymmetric random tables, an independent implementation and a set of deliberate mistakes each caught something the others would not. More dynamic programming, from the knapsack problem onwards, is in the algorithms section.

Source Code and Tests

All programs on this page are in the dynamic-programming/sequence-alignment directory of the MYCPLUS C and C++ examples repositories:

LanguageRepository directoryBuild
Cmycplus/c-examples › dynamic-programming/sequence-alignmentSequence alignment C build status
C++mycplus/cpp-examples › dynamic-programming/sequence-alignmentSequence alignment C++ build status

Build and test either one:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the build checks. The C version compiles with GCC and Clang under C11 and C17 and with MSVC /W4 /WX; the C++ version with g++ and clang++ under C++17 and C++20 and with MSVC /W4 /WX /permissive-; warnings are errors. Both check the textbook results, random pairs against a brute force over every alignment (5,000 in C, 2,000 in C++) and long protein pairs, and both print exactly the outputs on this page. On Linux, the workflows run everything under AddressSanitizer and UndefinedBehaviorSanitizer, and the C workflow also checks that the letter_index pitfall is caught, that 600 alignments agree with Biopython, and that each mutation is caught. They do not run the benchmark, whose figures came from one machine.

What I Verified

Each example directory contains run_all.sh for Ubuntu and WSL and run_all.ps1 for Windows, which run every check below and print one line per row.

CheckUbuntu 24.04WSL (Ubuntu)Windows (MSVC)
C: build and CTest, GCC 13.3 and Clang 18.1.3, C11 and C17Pass (7 of 7 tests)Pass (7 of 7 tests)Not applicable
C: build with MSVC /W4 /WX and CTestNot applicableNot applicablePass (7 of 7 tests)
C: 5,000 brute-force pairs, 200 long pairs, known resultsPass (0 failed)PassPass
C: AddressSanitizer and UndefinedBehaviorSanitizerPass (GCC)Pass (GCC)Not applicable
C: Valgrind on the test suitePass (0 errors, no leaks)PassNot applicable
C: letter_index caught by the sanitizersPassPassNot applicable
C: agrees with Biopython, 600 alignmentsPass (600 of 600, Biopython 1.88)Pass (600 of 600, Biopython 1.83)Not applicable
C: ten mutations caught, two equivalent changes passPassPassNot applicable
C++: build and CTest, g++ and clang++, C++17 and C++20Pass (2 of 2 tests)PassNot applicable
C++: build with MSVC /W4 /WX /permissive- and CTestNot applicableNot applicablePass (2 of 2 tests)
C++: AddressSanitizer, UBSan and ValgrindPassPassNot applicable
BenchmarkRun on the cloud VM, figures aboveNot runNot run

Not covered: 32-bit builds, compilers newer than GCC 13.3 and Clang 18.1.3, Clang’s sanitizers on the test machine (they run in CI), timing on any other machine, real genomic or protein data beyond the textbook examples, and scoring with fractional gap costs: both versions use integer scores.

Scroll to Top