IAE Academy

FOR CORE AND IT JOBS · CHAPTER 2 OF 7

Pairwise sequence alignment

This chapter explains why sequences are aligned, how an alignment is scored with gap penalties and substitution matrices, and how global (Needleman-Wunsch) and local (Smith-Waterman) alignments are found by dynamic programming. Searching a new sequence against known ones builds on these methods.

Updated 30 Oct 2026

What you will be able to do

You will say why two sequences are aligned and how an alignment gets a score. You will choose between a linear and an affine gap penalty and read a protein substitution matrix. You will fill the score table for global alignment, trace back the alignment, and say exactly what changes for local alignment.

Before you start

  1. Chapter 1, Biological data and databases

  2. Logarithms, including base 2:

  3. Probability: a frequency as a fraction, and multiplying the probabilities of independent events

  4. Summation notation

  5. Taking the largest of a few numbers

  6. Filling a table row by row from cells already filled

  7. Big-O notation for how work grows with input size

Scoring an alignment

Each unit of a sequence, a nucleotide in DNA or an amino acid in a protein, is a residue. Sequences that descend from a common ancestor are homologous. Residues a molecule needs in order to work tend to change slowly, so conserved stretches point to shared ancestry and often shared function; high similarity is evidence of homology, not proof. An alignment lines two sequences up so that matching residues share a column, with a dash where one has a residue the other lacks (an insertion or a deletion). DNA is written 5' to 3' in capitals ACGT, and an alignment as two monospace rows, top over bottom.

ALIGNMENT SCORE

Holds with a linear gap penalty, each column scored on its own. is the number of columns; are the symbols in column (at most one is a gap). For DNA, for a match, for a mismatch, for a gap (). For proteins, a residue pair scores from a substitution matrix. Scores have no unit; higher is better.

GAP PENALTY OF LENGTH K

A gap is consecutive gap symbols in one sequence; is the penalty per position. Affine: opens (first position), extends (each further one), usually ; gives the linear form. With , one gap costs less than several gaps of the same total length, which fits one insertion event adding several residues.

WORKED EXAMPLE

Score the alignment ATGCCT (top row) over AT--CT (bottom row) with match +2 and mismatch -1. Use a linear gap penalty and then an affine one with , . What would two separate gaps of length 1 cost in each case?

Solution
  1. Read the columns: A/A, T/T, C/C and T/T are 4 matches, worth , and there is no mismatch.

  2. The columns G/- and C/- have their gap symbols next to each other in the bottom row, so they are one gap of length .

  3. Linear: each gap position costs , so and .

  4. Affine: the first position costs and the second , so and .

  5. Two separate gaps of length 1: each is a first position. Linear , the same as one gap of 2. Affine , far worse than .

Answer: Linear , affine . Two single gaps cost (linear) or (affine).

Protein substitution matrices

Proteins are built from 20 standard amino acids, and they are not equally interchangeable. Leucine for isoleucine is a common, mild change; leucine for tryptophan is rare. So every pair gets its own score, held in a symmetric 20 by 20 table. The score compares how often the pair is aligned in trusted homologous alignments with how often chance alone would pair them. Treating columns as independent, the odds of a whole alignment are the product of its column odds, and a logarithm turns that product into the sum used in .

LOG-ODDS SUBSTITUTION SCORE

: fraction of aligned pairs in trusted alignments that are . , : background frequencies, so is the chance of a random pairing and the ratio is the odds. sets the scale: a unit of is a bit, so is in bits. : more often than chance. BLOSUM uses (half-bits), rounded to whole numbers.

PAM

BLOSUM

Built from

Changes counted between closely related proteins (one step = 1 accepted change per 100 residues), then that step applied repeatedly

Conserved, ungapped blocks of related proteins

The number means

Evolutionary distance, in accepted changes per 100 residues

Sequences at least that percent identical are grouped and counted once (BLOSUM62: 62%)

BLOSUM62 is built at an intermediate threshold, and its scores work well across a broad range of similarity, from close to fairly distant proteins. So it is a common default when you do not know in advance how closely two proteins are related.

WATCH OUT FOR

PAM and BLOSUM numbers run in opposite directions. Test: ask what the number counts. PAM250 counts a long distance (distant sequences); BLOSUM80 a high identity (close sequences).

Global alignment: Needleman-Wunsch

Write X for the sequence of length (symbols ) and Y for the one of length (). Take the best alignment of the first symbols of X with the first of Y. Its last column is with , with a gap, or with a gap, since two gaps never share a column. With a linear gap penalty, the columns before it must form a best alignment of the shorter prefixes: a better one would raise the total. So each table cell is the best of three options built from smaller cells, without listing the explosively many alignments. This is dynamic programming.

GLOBAL RECURRENCE

Holds for a linear gap penalty , , . is the best score of the first symbols of X against the first of Y. Lines: diagonal ( with ), up ( against a gap), left ( against a gap). Affine: a gap position costs if it opens a gap and if it extends one, which depends on how the shorter alignment ended, so three tables are kept, for alignments ending diagonal, up and left.

BOUNDARY AND ANSWER

Aligning symbols against nothing needs gaps. Row 0 and column 0 stand for the empty prefix (no symbols yet) and are labelled - in the tables below. The best global score is the bottom right cell.

-

G

T

C

-

0

-1

-2

-3

G

-1

1

0

-1

A

-2

0

0

-1

T

-3

-1

1

0

C

-4

-2

0

2

WORKED EXAMPLE

Align X = GATC (rows) with Y = GTC (columns) globally with match +1, mismatch -1, linear gap -1. The filled table is above. Find the best score and an alignment.

Solution
  1. Boundary: each gap costs 1, so row 0 reads 0, -1, -2, -3 and column 0 reads 0, -1, -2, -3, -4.

  2. Cell (1,1): G with G matches. Diagonal beats up and left, both . So 1.

  3. Cell (2,1): A with G mismatches. Diagonal , up , left . The maximum is 0, from up.

  4. Cell (3,2): T with T matches. Diagonal , up , left . So 1.

  5. Cell (4,3): C with C matches. Diagonal , up , left . So the score is 2.

  6. Traceback from (4,3): each step goes back to the neighbour that gave the value. Diagonal (C/C), diagonal (T/T), up (A against a gap), diagonal (G/G).

  7. Read forwards, the rows are GATC over G-TC. Rescoring: 3 matches give +3 and one gap gives -1, so 2, equal to the corner.

Answer: Best score 2, with the alignment GATC over G-TC. If two neighbours tie, either may be followed, giving more than one best alignment.

WATCH OUT FOR

The table fills from the top left but the alignment is read from the bottom right. Test: rescore the alignment you recovered; it must equal .

COST OF THE TABLE

Time is in any case: the table has cells, each a fixed amount of work. Memory is also when the whole table is kept for the traceback. Local alignment costs the same.

Local alignment: Smith-Waterman

Global alignment forces all of both sequences into the alignment, but two proteins may share only one domain, with unrelated stretches around it. Local alignment finds the best-scoring pair of segments instead. A stretch that scores badly is dropped rather than paid for: the running score is not allowed below zero, and it restarts. This needs a random pair of residues to score below zero on average, with some scores positive. Otherwise extending an alignment tends to raise its score, and local alignment behaves like global alignment.

LOCAL RECURRENCE

Holds for a linear gap penalty , with as in the alignment score. Boundary: . The best local score is the largest anywhere in the table, not the corner. Traceback starts at that cell and stops on reaching a cell with ; that cell's pair is not part of the alignment.

-

G

C

A

-

0

0

0

0

A

0

0

0

1

G

0

1

0

0

C

0

0

2

1

T

0

0

1

1

WORKED EXAMPLE

Find the best local alignment of X = AGCT (rows) and Y = GCA (columns) with match +1, mismatch -1, linear gap -1. The filled table is above.

Solution
  1. Boundary: row 0 and column 0 are all 0.

  2. Row A: the only match is with the A heading column 3, so that cell holds . Every other cell in the row would go negative, so the floor gives 0.

  3. Cell (2,1): G with G matches, diagonal .

  4. Cell (3,2): C with C matches, diagonal . This is the largest value in the table.

  5. Traceback from (3,2): diagonal to (2,1), value 1, then diagonal to (1,0), value 0. Stop.

  6. The aligned segments are GC over GC. The A and T of X and the A of Y are left out.

Answer: Best local alignment GC over GC, score 2. The corner cell (4,3) holds only 1, so reading the corner would miss it.

IN ONE LINE

The zero floor lets an alignment start anywhere, and taking the largest cell lets it end anywhere.

Check yourself

CHECK YOURSELF 1

In local alignment, why is a zero included in the maximum of the recurrence?

  1. (A)

    So that no gap is ever allowed

  2. (B)

    So that a badly scoring region restarts the alignment instead of lowering the score of a good one

  3. (C)

    So that the answer is always in the bottom right cell

  4. (D)

    So that mismatches score zero

Answer and solution

Answer: (B)

  1. A zero means: start a new alignment at this cell.

  2. This stops a poor stretch from dragging down a good segment before it.

  3. The answer is the largest cell anywhere, not the corner, and mismatch and gap scores stay negative, so only B holds.

CHECK YOURSELF 2One or more options are correct

Which statements about substitution matrices are correct?

  1. (A)

    A higher BLOSUM number is built from more closely related blocks

  2. (B)

    A higher PAM number models more evolutionary distance

  3. (C)

    A positive score means the pair is seen in homologous alignments more often than chance

  4. (D)

    BLOSUM62 scores are raw counts of identical residues

Answer and solution

Answer: (A), (B), (C)

  1. The BLOSUM number is the identity threshold for grouping sequences; a higher threshold means the counts come from closer pairs: A is true.

  2. PAM numbers count accepted changes per 100 residues, an evolutionary distance: B is true.

  3. A log-odds score above zero means the pair occurs more often than the background product: C is true.

  4. Scores are rounded log-odds, not counts of identities: D is false.

CHECK YOURSELF 3

Align X = AG (rows) with Y = AC (columns) globally with match +1, mismatch -1 and a linear gap penalty of -2 per position. What is the best global alignment score?

Answer and solution

Answer: (accepted range )

  1. Boundary: first row 0, -2, -4; first column 0, -2, -4.

  2. F(1,1): A with A, .

  3. F(1,2): A with C, diagonal , up , left . So .

  4. F(2,1): G with A, diagonal , up , left . So .

  5. F(2,2): G with C, diagonal , up , left . So 0, the alignment AG over AC.

CHECK YOURSELF 4

A local alignment table uses match +2, mismatch -1 and a linear gap penalty of -2. For a cell whose two residues differ, the diagonal neighbour holds 1, the cell above holds 3 and the cell to the left holds 0. What value does the cell take?

  1. (A)

    0

  2. (B)

    1

  3. (C)

    2

  4. (D)

    -1

Answer and solution

Answer: (B)

  1. Diagonal: .

  2. Up: .

  3. Left: .

  4. Floor: 0.

  5. The maximum of is 1.

Used in these GATE topics