Lesson 5.8

Backtracking in the Alignment Graph

4 min read2 code challenges✓ Read

Watch the lectureDynamic Programming and Backtracking Pointers

Recall that we previously highlighted each edge selected by ManhattanTourist, as shown below.

To form a longest path, we simply need to find a path from source to sink formed by highlighted edges (more than one such path may exist). However, if we were to walk from source to sink along the highlighted edges, we might reach a dead end, such as the node (1, 2). In contrast, every path from the sink will bring us back to the source if we backtrack in the direction opposite to each highlighted edge, as shown below.

Figure: Following edges from the sink backwards to the source produces the red path in the DAG above, which highlights a longest path from the source to sink.

The animation below shows a longest path being recovered from the backtracking pointers. Every node remembers the single edge it scored best from, and the edges that no node chose fade to gray. Following the remembered edges backward from the sink to the source traces the highest-scoring path, whose weights 1 + 3 + 6 + 7 + 5 + 8 + 2 + 2 sum to the 34 that was already waiting at the sink.

We can use this backtracking idea to construct an LCS of strings v and w. We know that if we assign a weight of 1 to the edges in AlignmentGraph(v, w) corresponding to matches and assign a weight of 0 to all other edges, then s_{|v|, |w|} gives the length of an LCS. The following algorithm maintains a record of which edge was used to compute each value s_{i, j} by utilizing backtracking pointers, which take one of the three values ↓ , →, or ↘. Backtracking pointers are stored in a matrix Backtrack.

LCSBackTrack(v, w)
  for i ← 0 to |v|
    si, 0 ← 0
  for j ← 0 to |w|
    s0, j ← 0
  for i ← 1 to |v|
    for j ← 1 to |w|
      match ← 0
      if vi-1 = wj-1
        match ← 1
      si, j ← max{si-1, j , si,j-1 , si-1, j-1 + match }
      if si,j = si-1,j
        Backtracki, j ← "↓"
      else if si, j = si, j-1
        Backtracki, j ← "→"
      else if si, j = si-1, j-1 + match
        Backtracki, j ← "↘"
  return Backtrack

STOP and Think How does changing the order of these three "if" statements affect the computation of Backtrack?

We now need to find a path from the source to the sink formed by the highlighted edges. The following algorithm solves the Longest Common Subsequence Problem by using the information in Backtrack. OutputLCS(Backtrack, v, i, j) outputs an LCS between the i-prefix of v and the j-prefix of w. The initial invocation that outputs an LCS of v and w is OutputLCS(Backtrack, v, |v|, |w|).

OutputLCS(backtrack, v, i, j)
  if i = 0 or j = 0
    return ""
  if backtracki, j = "↓"
    return OutputLCS(backtrack, v, i - 1, j)
  else if backtracki, j = "→"
    return OutputLCS(backtrack, v, i, j - 1)
  else
    return OutputLCS(backtrack, v, i - 1, j - 1) + vi

STOP and Think OutputLCS is a recursive algorithm, but it is efficient. What makes it different from the inefficient recursive algorithms for making change and finding a longest path in a DAG?

Code Challenge Use OutputLCS (reproduced below) to solve the Longest Common Subsequence Problem. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

• Input: Two strings s and t.
• Output: A longest common subsequence of s and t.

OutputLCS(backtrack, v, i, j)
  if i = 0 or j = 0
    return ""
  if backtracki, j = "↓"
    return OutputLCS(backtrack, v, i - 1, j)
  else if backtracki, j = "→"
    return OutputLCS(backtrack, v, i, j - 1)
  else
    return OutputLCS(backtrack, v, i - 1, j - 1) + vi

Try it Fill the alignment grid and backtrack, one cell at a time

Ready to write it yourself? Implement alignment with backtracking in the interactive text.

The backtracking method can be generalized to construct a longest path in any DAG. Whenever we compute s_b as

we simply need to store a predecessor of b that was used in the computation of s_b so that we can backtrack later on. You are now ready to use backtracking to find the longest path in an arbitrary DAG.

Code Challenge Solve the Longest Path in a DAG Problem. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

• Input: An integer representing the starting node to consider in a graph, followed by an integer representing the ending node to consider, followed by a list of edges in the graph. The edge notation "0->1:7" indicates that an edge connects node 0 to node 1 with weight 7.  You may assume a given topological order corresponding to nodes in increasing order.
• Output: The length of a longest path in the graph, followed by a longest path.

Exercise Break Currently, OutputLCS finds a single LCS of two strings. Modify OutputLCS (and LCSBacktrack) to find every LCS of two strings.