Lecture 1.4

Sequence alignment

Learning objectives

After this lecture, you should be able to do the following.

Predict how a change in scoring parameters changes the optimal alignment, and choose the method and penalties that fit a pair of sequences.

  1. Predict how raising the gap penalty changes an optimal alignment.
  2. Diagnose which alignment method and gap penalty suit a pair of sequences from their lengths and expected region of similarity.

Read the score an alignment charges for a substitution and for a gap, and explain why a gap carries a penalty of its own.

  1. Explain why an alignment scores a gap with its own penalty, separate from a mismatch, and contrast a linear penalty that scales with gap length against an affine penalty that charges more to open a gap than to extend it.
  2. Read a match or mismatch score from a substitution matrix, and interpret its sign.

Explain why dynamic programming finds the optimal alignment without enumerating alignments, and work a short global alignment through the matrix.

  1. Explain why dynamic programming beats enumerating every alignment.
  2. Determine the optimal global alignment score for a short pair of sequences by filling a Needleman-Wunsch matrix, and trace back the alignment it came from.

Contrast global with local alignment, and work a short local alignment through the matrix.

  1. Contrast global and local alignment, and say when each is used.
  2. Determine the optimal local alignment score for a short pair of sequences by filling a Smith-Waterman matrix with its floor of zero, and trace back from the highest-scoring cell.

Readings

Supplemental

DEKM ch. 2, §2.1 and §2.3
DEKM sets up the alignment problem in 2.1, then 2.3 gives the two core fills, Needleman-Wunsch for global and Smith-Waterman for local, with a boxed note on the \(O(nm)\) cost. Work one small matrix of each kind by hand. The global fill starts its traceback in the corner, the local fill starts at the largest cell and stops at a zero. That one difference is {lo-global-vs-local}. The repeated-match and overlap-match variants are edge cases, not needed here.
(T 2, 5, 6, 7, 8)
DEKM ch. 2, §2.2
The scoring model: substitution matrices read as log-odds, and the choice between a linear and an affine gap penalty. Be able to say why a matrix entry is positive or negative, and why one long gap should not cost as much as many short ones. That second point is what motivates affine penalties in 2.4. Leave the PAM and BLOSUM derivations in 2.8 for now. You do not need them to read a matrix.
(T 3, 4)
LAM ch. 5, scoring schemes and the dynamic-programming algorithm, Example 5.5
Lesk gives a second pass at scoring schemes and a fully worked dynamic-programming example. Redo Example 5.5 yourself before class. A worked matrix in another author’s notation is the fastest way to check you can fill and trace one. The Perl programs in the boxes are not needed. This course writes no code.
(T 3, 4, 6)
CS ch. 3
Noe’s chapter builds alignment from edit operations, with clean notation for gaps and the recurrence. Read this if DEKM feels terse. The edit-operation view makes gaps easy to picture.
(T 3, 6, 7)
HY ch. 4, §4.1
A plain-language pass over local alignment, global alignment, and gap penalties. A gentle warm-up if the DEKM sections move too fast. Read it first, then go to DEKM for the matrix work. Its tool lists are not the point here.
(T 3, 7)
NW70 A general method applicable to the search for similarities in the amino acid sequence of two proteins
The 1970 paper that introduced the matrix method for global alignment. See where the modern recurrence came from. Their scoring is simpler than ours, a match counts one, which makes the original easy to read.
(T 5, 6)
SW81 pp. 195-197
The three-page letter that defined local alignment with a zero floor on the score matrix. Read Figure 1. The one worked matrix, with the traceback from the largest cell down to a zero, is the clearest statement of what makes an alignment local.
(T 7, 8)
WSB76 pp. 367-387
Defines sequence distance as a true metric and allows gaps of any length. Take the triangle inequality as the reason a distance between sequences is well behaved. The general gap weight here is the ancestor of the affine penalty.
(T 3)
Back to top