Lesson 5.7

From Manhattan to an Arbitrary DAG

6 min read✓ Read

Watch the lectureFrom Manhattan to the Alignment Graph

Sequence alignment as building a Manhattan-like graph

After seeing how dynamic programming solved the Manhattan Tourist Problem, you should be prepared to adapt ManhattanTourist for alignment graphs with diagonal edges. 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 have 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" in the print companion or at Cogniterra 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.

Dynamic programming in an arbitrary DAG

Given a node b in a DAG, let s_b denote the length of the longest path from the source to b. We call node a a predecessor of node b if there is an edge connecting a to b in the DAG; the indegree of a node is equal to the number of its predecessors. The score s_b of node b with indegree k is computed as a maximum of k terms:

For example, in the graph shown below, 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 have already computed s_{0, 0}, s_{0, 1}, and s_{1, 0}, we can therefore compute s_{1, 1} as the maximum of three values.

Figure: In the DAG above, (1, 1) has three predecessors  ((0, 0), (0, 1), and (1, 0)) that are used in the computation of s_{1, 1}.

An analogous argument can be applied to the alignment graph (below) to compute the length of an LCS between sequences v and w. Since in this case all edges have weight 0 except for diagonal edges of weight 1 that represent matches (v_i = w_j), we obtain the following recurrence for computing the length of an LCS.

STOP and Think The above recurrence does not incorporate mismatch edges. Why is this not a problem?

A similar approach can be developed to find the longest path in any DAG, as suggested by the next exercise.

Exercise Break What is the length of a longest path between the blue and red nodes in the DAG shown below? Check your solution at Cogniterra.

Topological orderings

Do not worry if you struggled to answer the last exercise. The hitch to using dynamic programming in order to find the length of a longest path in a DAG is that we must decide on the order in which to visit nodes when computing the values s_b according to the recurrence

This ordering of nodes is important, since by the time we reach node b, the values s_a for all its predecessors must have already been computed. We have managed to hide this issue for rectangular grids because the order in which we have computed the s_{i, j} ensured that we would never consider a node before visiting all of its predecessors.

To illustrate the importance of visiting nodes in the correct order, consider the DAG shown below, which corresponds to a “Dressing Challenge Problem”. How would you order the nodes of this graph so that you don't put on your boots before your tights.

To solve the Dressing Challenge Problem, we need to arrange the nodes in the DAG from the previous step along a line so that every directed edge connects a node to a node on its right (see figure below). To get dressed without any mishaps, you can simply visit nodes from left to right. To find a longest path in an arbitrary DAG, we first need to order the nodes of the DAG so that every node falls after all its predecessors. Formally, an ordering of nodes (a₁, ... , a_k) in a DAG is called a topological ordering if every edge (a_i, a_j) of the DAG connects a node with a smaller index to a node with a larger index, i.e., i < j.

Figure: Two different topological orderings of the Dressing Challenge DAG.

Exercise Break How many topological orderings does the Dressing Challenge DAG (reproduced below) have? Check your solution at Cogniterra.

ManhattanTourist is able to find a longest path in a rectangular grid because its pseudocode (reproduced at bottom) implicitly orders nodes according to the “row-by-row” topological ordering shown in the figure below.

ManhattanTourist(n, m, Down, Right)
  s0, 0 ← 0
  for i ← 1 to n
    si, 0 ← si-1, 0 + downi, 0
  for j ← 1 to m
    s0, j ← s0, j−1 + right0, j
  for i ← 1 to n
    for j ← 1 to m
      si, j ← max{si - 1, j + downi, j, si, j - 1 + righti, j}
  return sn, m

The “column-by-column” topological ordering, shown below, gives yet another topological ordering of a rectangular grid.

STOP and Think Rewrite the ManhattanTourist pseudocode based on the additional topological ordering shown below.

It can be proven that any DAG has a topological ordering, and that this topological ordering can be constructed in time proportional to the number of edges in the graph (for more details, see "DETOUR: Constructing a Topological Ordering" in the print companion or at Cogniterra). Once we have a topological ordering, we can compute the length of the longest path from source to sink by visiting the nodes of the DAG in the order dictated by the topological ordering, which is achieved by the following algorithm. For simplicity, we assume that the source node is the only node with indegree 0 in Graph.

LongestPath(Graph, source, sink)
  for each node b in Graph
    sb ← −∞
  ssource ← 0
  topologically order Graph
  for each node b in Graph (following the topological order)
    sb ← maxall predecessors a of node b {sa + weight of edge from a to b}
  return ssink

Since every edge participates in only a single recurrence, the runtime of LongestPath is proportional to the number of edges in the DAG Graph.

We can now efficiently compute the length of a longest path in an arbitrary DAG, but we do not yet know how to convert LongestPath into an algorithm that will construct this longest path. In the next section, we will use the Longest Common Subsequence Problem to explain how to construct a longest path in a DAG.