From Manhattan to an Arbitrary Directed Acyclic Graph

After seeing how dynamic programming solved the Manhattan Tourist problem, we should be prepared to adapt ManhattanTourist for alignment graphs with diagonal edges.

Sequence alignment as building a Manhattan-like graph

Recall the figure below, in which we modeled the Longest Common Subsequence Problem as finding the longest path in an alignment graph “city” whose “attractions”’ (matches) all lie on diagonal edges with weight 1.

You can probably work out the recurrence relation for the alignment graph on your own, but imagine for a second that you’ve not already learned that an LCS can be represented by a longest path in the alignment graph. As DETOUR: Finding a Longest Common Subsequence without Building a City explains, we don’t need to build a Manhattan-like city to compute the length of an LCS. However, the arguments required to do so are tedious. More importantly, various alignment applications are much more complex than the Longest Common Subsequence Problem and require building a DAG with appropriately chosen edge weights in order to model the specifics of a biological problem. Rather than treating each subsequent alignment application as a frightening new challenge, we would like to equip you with a generic dynamic programming algorithm that will find a longest path in any DAG. Moreover, many bioinformatics problems have nothing to do with alignment, yet they can also be solved as applications of the Longest Path in a DAG Problem.

For example, in the graph shown here (bottom right), node (1, 1) has three predecessors. You can arrive at (1, 1) by traveling right from (1, 0), down from (0, 1), or diagonally from (0, 0), Assuming that we’ve already computed $s_{0, 0}$, $s_{0, 1}$, and $s_{1, 0}$, we can therefore compute ...