Lesson 5.4
Sequence Alignment is the Manhattan Tourist Problem in Disguise
Below, we add two arrays of integers to an alignment of ATGTTATA and ATCGTCC. The array [0 1 2 2 3 4 5 6 7 8] holds the number of symbols of ATGTTATA used up to a given column in the alignment. Similarly, the array [0 1 2 3 4 5 5 6 6 7] holds the number of symbols of ATCGTCC used up to a given column.
We add a third array [↘ ↘ → ↘ ↘ ↓ ↘ ↓ ↘] recording whether each column represents a match/mismatch (↘/↘), an insertion (→), or a deletion (↓).
This third array corresponds to a path from source to sink in an 8 × 7 rectangular grid. The i-th node of this path is made up of the i-th element of [0 1 2 2 3 4 5 6 7 8] and the i-th element of [0 1 2 3 4 5 5 6 6 7]:
(0. 0) ↘ (1, 1) ↘ (2, 2) → (2, 3) ↘ (3, 4) ↘ (4, 5) ↓ (5, 5) ↘ (6, 6) ↓ (7, 6) ↘ (8, 7)
This path is shown in the figure below. Note that in addition to horizontal and vertical edges, we have added diagonal edges connecting (i, j) to (i + 1, j + 1).
We call this DAG (reproduced below) the alignment graph of strings v and w, denoted AlignmentGraph(v, w), and we call a path from source to sink in this DAG an alignment path. Every alignment of v and w can be viewed as a set of instructions to construct a unique alignment path in AlignmentGraph(v, w), where each match/mismatch, insertion, and deletion corresponds to an edge ↘/↘, →, and ↓, respectively. Thus, each alignment of strings v and w corresponds to a path in AlignmentGraph(v, w), and vice-versa.
STOP and Think Can you use the alignment graph to find a longest common subsequence of two strings?
Exercise Break Construct the alignment of ATGTTATA and ATCGTCC corresponding to the alignment path shown below. Solve at Cogniterra.
Recall that finding a longest common subsequence of two strings is equivalent to finding an alignment of these strings maximizing the number of matches. In the figure below, we highlight all diagonal edges of AlignmentGraph(ATGTTATA, ATCGTCC) corresponding to matches. If we assign a weight of 1 to all these edges and 0 to all other edges, then the Longest Common Subsequence Problem is equivalent to finding a longest path in this weighted DAG! Thus, we need to design an algorithm for the Longest Path in a DAG Problem, but to do so, we need to know more about dynamic programming, a powerful algorithmic paradigm that is used for solving thousands of problems from various scientific fields.
Figure: AlignmentGraph(ATGTTATA, ATCGTCC) with all edges of weight 1 colored red (all other edges have weight 0). These edges correspond to potential matched symbols in an alignment of the two strings.