Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 49 ยท Sequence Alignment

Chapter 3 overview: sequence alignment

Chapter 3 introduces sequence alignment: why we align, how scoring works, the dynamic programming algorithms, BLAST and multiple sequence alignment.

If one idea defines bioinformatics, it is sequence alignment. Two sequences that descend from a common ancestor accumulate changes over time: substitutions, insertions and deletions. Alignment lays one sequence beside the other, inserting gaps where needed, so that positions that share an ancestor line up in the same column. From a good alignment you can read off how similar two genes are, find a gene's relatives in a database, predict what a new protein does, and build the evolutionary trees of chapter 4.

Two aligned DNA sequences with matches, one mismatch and one gap, and cards explaining the scores
Caption: an alignment is a hypothesis about which positions share an ancestor, scored by rewarding matches and penalizing mismatches and gaps.

What you will learn

  • Why alignment is the central operation of sequence analysis.
  • The difference between global, local and multiple alignment.
  • How the lessons of this chapter fit together.

The big picture

Alignment answers three kinds of question. Pairwise questions compare two sequences: how similar are these two proteins? Database questions compare one sequence against millions: what is this unknown gene like? Multiple questions compare many sequences at once: which positions never change across the whole family? The algorithms differ, but they share one idea: score every possible way of lining the sequences up, then pick the best-scoring one without trying every possibility.

That last part is the algorithmic heart of the chapter. The number of possible alignments of two sequences of length 1,000 is astronomically large, yet dynamic programming finds the best in about a million steps. When even that is too slow (a database of billions of residues), heuristics such as BLAST trade a little sensitivity for a great deal of speed.

Two kinds of pairwise alignment

Global Align end to end
Local Find the best matching region
1 / 3

What each lesson covers

  1. Scoring matrices and gap penalties explains how scores are chosen, with log-odds, BLOSUM62 and affine gaps.
  2. Global alignment: Needleman-Wunsch fills a dynamic programming matrix and traces back the optimal alignment.
  3. Local alignment: Smith-Waterman adds one rule, a floor of zero, to find the best shared region.
  4. BLAST and heuristic search shows how seeds, extension and E-values make database search fast and interpretable.
  5. Multiple sequence alignment covers progressive alignment, conservation and consensus.
  6. Chapter 3 review summarizes everything with a ten-question quiz.

A short history

Sequence comparison is older than DNA sequencing. In 1970 Saul Needleman and Christian Wunsch published the first dynamic programming method for aligning two protein sequences end to end. In 1981 Temple Smith and Michael Waterman modified it to find the best local region. In the 1980s David Lipman and William Pearson's FASTA made database search practical on the computers of the day, and Margaret Dayhoff's atlas of protein sequences had already shown the value of comparing proteins systematically. In 1990 Stephen Altschul and colleagues introduced BLAST, whose combination of speed and statistical rigor made it the default search tool.

The pattern is typical of the field: a clean algorithm first, a fast heuristic when data outgrew it, and a statistical framework to say when a result means something. As you work through the chapter, look for that pattern repeating at each stage.

Common misconceptions

  • "There is one correct alignment." The best alignment depends on the scoring scheme, and distantly related sequences may have several near-optimal alignments.
  • "High similarity proves common ancestry; low similarity disproves it." Similarity is evidence of homology, and homology is a yes-or-no statement, not a percentage.

Try it

Python Count the possible alignments

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.

Align by eye

Check your understanding

Quick check ยท 3 questions

of 3 answered You scored / 3 ยท perfect!

  1. 1. What is the main purpose of aligning two sequences?

    An alignment hypothesizes which positions descend from a common ancestral position.
  2. 2. Why is dynamic programming needed for alignment?

    Dynamic programming finds the optimal alignment without enumerating all possibilities.
  3. 3. Which problem needs multiple sequence alignment?

    Conservation across many sequences needs them aligned together.

Summary

  • Alignment lines up positions that share an ancestor, using gaps for insertions and deletions.
  • Scoring schemes define "best"; dynamic programming finds it; BLAST makes it fast.
  • Multiple alignment extends the idea to families of sequences.

Next: Scoring matrices and gap penalties