Backtracking in the Alignment Graph
Explore how backtracking in alignment graphs helps find longest common subsequences between two strings. Understand the use of backtracking pointers, recursive algorithms, and how this method applies to finding longest paths in directed acyclic graphs. Gain practical skills to implement sequence comparison algorithms and modify them to find all possible subsequences.
We'll cover the following...
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 (figure below).
Backtracking
We can use this backtracking idea to construct an LCS of strings and . 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 ...