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.