Lesson 5.2
Introduction to Sequence Alignment
Watch the lectureThe Alignment Game and the Longest Common Subsequence Problem
Sequence alignment as a game
To simplify matters, we will compare only two sequences at a time, returning to multiple sequence comparison at the end of the chapter. The Hamming distance, which counts mismatches in two strings, rigidly assumes that we align the i-th symbol of one sequence against the i-th symbol of the other. However, since biological sequences are subject to insertions and deletions, it is often the case that the i-th symbol of one sequence corresponds to a symbol at a completely different position in the other sequence. The goal, then, is to find the most appropriate correspondence of symbols.
For example, ATGCATGC and TGCATGCA have no matching positions, and so their Hamming distance is equal to 8:
ATGCATGC
TGCATGCA
Yet these strings have seven matching positions if we align them differently:
ATGCATGC-
-TGCATGCA
Strings ATGCTTA and TGCATTAA have more subtle similarities:
ATGC-TTA-
-TGCATTAA
These examples lead us to postulate a notion of a good alignment as one that matches as many symbols as possible.
You can think about maximizing the number of matched symbols in two strings as a single-person game. At each turn, you have two choices. You can remove the first symbol from each sequence, in which case you earn a point if the symbols match; alternatively, you can remove the first symbol from either of the two sequences, in which case you earn no points but may set yourself up to earn more points in later moves. Your goal is to maximize the number of points.
In the figure below, we show one way of playing this game for the sequences ATGTTATA and ATCGTCC, scoring 4 points. Any time we remove a symbol on the left, we add it to a growing alignment of ATGTTATA and ATCGTCC on the right. When only one symbol is removed in a turn, we align it with a space symbol.
Figure: One way of playing the alignment game for the strings ATGTTATA and ATCGTCC, with score 4. At each step, we choose to remove either one or both symbols from the left of the two sequences in the “remaining symbols” column. If we remove both symbols, then we align them in the “growing alignment”. If we remove only one symbol, then we align this symbol with a space symbol in the growing alignment. Matched symbols are shown in red (and receive score 1). Mismatched symbols are shown in purple; symbols aligned against space symbols are shown in blue or green depending on which sequence they were removed from.
The figure on the previous step, reproduced below, shows just one of many possible ways to play the alignment game for the strings ATGCATGC and TGCATGCA. Can you find an even better way to play this game for the strings?
Sequence alignment and the longest common subsequence
We now define an alignment of sequences v and w as a two-row matrix such that the first row contains the symbols of v (in order), the second row contains the symbols of w (in order), and space symbols (called gap symbols and shown as dashes below) may be interspersed throughout both strings, as long as two space symbols are not aligned against each other. Here is the alignment of ATGTTATA and ATCGTCC from the figure on the previous step.
A T - G T T A T A
A T C G T - C - C
An alignment presents one possible scenario by which v could have evolved into w. Columns containing the same letter in both rows are called matches and represent conserved nucleotides, whereas columns containing different letters are called mismatches and represent single-nucleotide substitutions. Columns containing a space symbol are called indels: a column containing a space symbol in the top row of the alignment is called an insertion, as it implies the insertion of a symbol when transforming v into w; a column containing a space symbol in the bottom row of the alignment is called a deletion, as it indicates the deletion of a symbol when transforming v into w. The alignment above has four matches, two mismatches, one insertion, and two deletions.
The matches in an alignment of two strings define a common subsequence of the two strings, or a sequence of symbols appearing in the same order (although not necessarily consecutively) in both strings. For example, the alignment above indicates that ATGT is a common subsequence of ATGTTATA and ATCGTCC. An alignment of two strings maximizing the number of matches therefore corresponds to a longest common subsequence (LCS) of these strings. Note that two strings may have more than one longest common subsequence.
Longest Common Subsequence Problem: Find a longest common subsequence of two strings.
- Input: Two strings.
- Output: A longest common subsequence of these strings.
Exercise Break Find all longest common subsequences of the strings ACTGCA and CATCGC. How many such subsequences did you find?
If we limit our attention to the two A-domains coding for Asp and Orn from the introduction, then in addition to the 19 matches that we have already found, we can find 10 more matches (shown in blue below), yielding a common subsequence of length 29.
STOP and Think What is the longest common subsequence of these strings?
None of the algorithmic approaches we have studied thus far will help us solve the Longest Common Subsequence Problem, and so before asking you to solve this problem, we will change course to describe a different problem that may seem completely unrelated to sequence alignment.