Sequence Alignment: Linear Space
How can we use $\Theta(m+n)$ space and $O(mn)$ time.
- Compute OPT(i,*) from OPT(i-1,*)
Edit distance graph
- Let f(i,j) be shortest path from (0,0) to (i,j).
- Observation: f(i,j) = OPT(i,j)
- Can compute f(*,j) for any j in O(mn) time and O(m+n) space.
- Let g(i,j) be shortest path from (i,j) to (m,n).
- Can compute g(*, j) by reversing the edge orientations and inverting the roles of (0,0) and (m,n): O(mn) time and O(m+n) space.
- What our goal now is to find shortest path from (0,0) to (m,n), which is f(i,j) + g(i,j).
- Let q be an index that minimizes f(q, n/2) + g(q, n/2). Then, the shortest path from (0, 0) to (m, n) uses (q, n/2).
- Find index q that minimizes f(q, n/2) + g(q, n/2) using DP.
- Recursively compute optimal alignment in each piece.
- Combine divide and conquer with dynamic programming
- O(mn) time to compute f(*, n/2) and g (*, n/2) and find index q.
- T(q, n/2) + T(m – q, n/2) time for two recursive calls.
Claim: T(m,n)≤ 2cmn
– Base cases: m=2 or n=2.
– Inductive hypothesis: T(m’,n’)≤ 2cm’n’ with m’<m and n’<n
Dijkstra limitation: positive path weight.
Now let’s allow negative weight(occurred in financial case)
Goal: Find path from s to t with largest gains or smallest loss.
Plus the negative number to removing negative edge.(shortest changed, because the numbers of edges of different path are different)
Negative cost cycle sum of cost is negative.
- If the graph contains negative cost cycle, there is no shortest path.
OPT(i,v) = length of shortest v-t path P using at most i edges
- Base case:
- v = t, OPT(i,v) = 0
- i = 0, OPT(i,v) = ∞
- Case 1: P uses at most i-1 edges.
- OPT(i,v) = OPT(i-1,v)
- Case 2: P uses exactly i edges.
- if (v, w) is first edge, then OPT uses (v, w), and then selects best w-t path using at most i-1 edges
- $\Theta(mn)$ time, $\Theta(n^2)$ space.
- No need to check edges of the form (v, w) unless M[w] changed in previous iteration.
- O(n) extra space
- Time: O(mn) worst case, but substantially faster in practice.
- Throughout the algorithm, M[v] is length of some v-t path, and after i rounds of updates, the value M[v] is no larger than the length of shortest v-t path using ≤ i edges.
Distance Vector Protocol
Dijkstra’s algorithm. Requires global information of network.
Bellman-Ford. Use only local knowledge of neighboring nodes.
Counting to infinity -> Path Vector Protocol
Negative Cycles in Graphs
Goal: find out negative cycles(if one exists)
Lemma If OPT(n,v) = OPT(n-1,v) for all v, then there is no negative cycle with a path to t.
- OPT(n,v) = OPT(n-1,v) => OPT(i,v) = OPT(n-1,v) for i ≥ n
- But negative cycle in a path implies that OPT(i,v) always decreases as i increases
Lemma If OPT(n,v) < OPT(n-1,v) for some node v, then (any) shortest path from v to t contains a cycle W. Moreover W has negative cost.
- Since OPT(n,v) < OPT(n-1,v), we know the shortest v-t path P has exactly n edges.
- By pigeonhole principle, P must contain a directed cycle W.
- Deleting W yields a v-t path with < n edges => W has negative cost.
Theorem Can detect negative cost cycle in O(mn) time.
- Add new node t and connect all nodes to t with 0-cost edge.
- Check if OPT(n, v) = OPT(n-1, v) for all nodes v.
- if yes, then no negative cycles
- if no, then extract cycle from shortest path from v to t