Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 49 ยท Sequence Alignment

Chapter 3 review: sequence alignment

Review sequence alignment: scoring, Needleman-Wunsch, Smith-Waterman, BLAST statistics and multiple alignment, with a one-page recap, practice code and a ten-question quiz.

Chapter 3 took you from the question "how similar are these two sequences?" to the machinery that answers it at the scale of whole databases. You met scoring schemes, two dynamic programming algorithms, a heuristic that makes search practical and the extension to many sequences. This review puts the pieces side by side, shows how they depend on each other and ends with a ten-question quiz.

Three cards: scoring, algorithms and many-sequence methods
Caption: scoring defines what 'best' means, algorithms find it, and BLAST and multiple alignment scale it up.

What you will learn

  • A recap table connecting the scoring, algorithm and statistics ideas.
  • How to choose among the methods for a given question.
  • Whether you are ready for phylogenetics in chapter 4.

The chapter in one table

Topic Key facts
Homology Common ancestry; yes or no. Similarity (percent identity) is evidence, not homology
Log-odds scoring S = (1/lambda) log(q / (p_a p_b)); BLOSUM62 is the default protein matrix
Gap penalties Affine: open plus extend; BLASTP default 11 and 1 (gap of length k costs 11 + k)
Needleman-Wunsch Global; H(i,j) = max(diag, up, left); first row and column are multiples of the gap; start traceback at the corner
Smith-Waterman Local; adds a floor of 0; start traceback at the maximum cell; needs negative expected random score
Complexity O(mn) time and space for pairwise dynamic programming
BLAST Seed words, two-hit extension, HSPs; heuristic
Statistics Bit score S' = (lambda S - ln K) / ln 2; E = m n 2^(-S'); E grows with database size
Multiple alignment Progressive (guide tree), iterative refinement, consistency; sum of pairs is NP-hard
Column summaries Conservation, consensus, profile, information content log2(A) - H

Choosing a method

Two sequences, same length?

Global Needleman-Wunsch
1 / 4

Worked review problems

Work these out on paper first.

  1. Score an alignment. With match +1, mismatch -1 and a linear gap of -2, the alignment ACGT-A over ACCTGA has four matches (A, C, T, A), one mismatch (G against C) and one gap, so its score is 4 - 1 - 2 = 1.
  2. Affine gaps. With open 11 and extend 1, a gap of 5 residues costs 16, while five separate gaps of length 1 cost 60. The scheme strongly prefers one long gap.
  3. E-value. A hit has bit score 40. In a search with query length 250 and database size 4 x 10^8 residues, E = 250 x 4e8 x 2^-40, which is about 0.091. The same hit in a database ten times larger would have E of about 0.91, which is no longer convincing, though its bit score is unchanged.

If any step was unclear, revisit the lesson on scoring or the BLAST lesson.

Where people go wrong

  • Quoting "percent homology". Quote percent identity or similarity; homology is yes or no.
  • Comparing E-values across databases. Compare bit scores, and remember E depends on database size.
  • Using global alignment for partial matches. A shared domain needs local alignment.
  • Trusting a single alignment. Gaps and boundaries in difficult regions vary between programs.
  • Forgetting the scoring scheme. Report the matrix, gap penalties and tool version.

Try it

Python Self-check: scoring and statistics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which method?

Check your understanding

Quick check ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. Which statement about homology is correct?

    Homology is about ancestry; similarity is evidence for it.
  2. 2. Which Needleman-Wunsch cell initialization is correct for gap penalty g?

    Aligning i letters against nothing costs i gaps.
  3. 3. Where does a Smith-Waterman traceback end?

    A zero marks the point where the local alignment began.
  4. 4. A BLASTP gap of length 4 with open 11 and extend 1 costs:

    Cost = 11 + 4 x 1 = 15.
  5. 5. How does the E-value change if the database becomes 100 times larger (same alignment)?

    E is proportional to database size.
  6. 6. What is the time complexity of pairwise dynamic programming alignment?

    The matrix has about m x n cells, each computed in constant time.
  7. 7. In progressive multiple alignment, what does the guide tree determine?

    Alignment proceeds from the most similar sequences outward along the tree.
  8. 8. What is the information content of a fully conserved protein column (maximum alphabet size 20)?

    Entropy is 0, so information is log2(20), about 4.32 bits.
  9. 9. Which BLAST program finds the protein that a DNA read may encode?

    BLASTX translates the nucleotide query in six frames and searches protein sequences.
  10. 10. Why must a local-alignment scoring scheme have a negative expected score for random pairs?

    With positive expected scores, alignments would grow with length even for unrelated sequences.

Summary

  • Scoring defines the best alignment; dynamic programming finds it; BLAST makes it fast; MSA extends it to families.
  • Always interpret scores with statistics: bit scores for comparison, E-values for chance.
  • Report the matrix, gap penalties and tool versions.
  • Chapter 4 uses multiple alignments as input to build evolutionary trees.

Next: Chapter 4 overview: phylogenetics