Backtracking in the Alignment Graph
Let’s explore backtracking and how we can use it in alignment graphs.
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 ...