Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:david:chapter6 [2011/03/30 00:34] – [6.6 - Sequence Alignment] margoliesd | courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) – [6.10 - Negative Cycles in a Graph] margoliesd | ||
---|---|---|---|
Line 39: | Line 39: | ||
====6.6 - Sequence Alignment==== | ====6.6 - Sequence Alignment==== | ||
- | The problem we are trying to solve is how to determine how alike two words or sequences are. We will use gaps and mismatches to determine the optimal value, where gaps all have constant cost and mismatches have variable cost depending on the symbols mismatched. Thus, the cost of M, our optimal solution, is the total of all gaps and mismatch costs, which is the lowest in the optimal solution. We define our sets as {1,2,..,n} and {1,2,..,m}, and note that for the optimal M, either (m,n) are in M (they match), or they do not. This leads us to the following recurrence, where either 1,2,or 3 is true. 1 - (m,n) is in M, 2 - the m< | + | The problem we are trying to solve is how to determine how alike two words or sequences are. We will use gaps and mismatches to determine the optimal value, where gaps all have constant cost and mismatches have variable cost depending on the symbols mismatched. Thus, the cost of M, our optimal solution, is the total of all gaps and mismatch costs, which is the lowest in the optimal solution. We define our sets as Y={1,2,..,n} and X={1,2,..,m}, and note that for the optimal M, either (m,n) are in M (they match), or they do not. This leads us to the following recurrence, where either 1,2,or 3 is true. 1 - (m,n) is in M, 2 - the m< |
+ | |||
+ | Readability 5/10. This was another difficult section to understand. | ||
+ | |||
+ | ====6.7 - Sequence Alignment in Linear Space via Divide and Conquer==== | ||
+ | |||
+ | The space requirement in the previous section is O(mn), but this can become 10 GB if both strings are 100,000 symbols each. We find that we can use a divide and conquer approach to divide the problem in many recursive calls, which allows for space to be reused by each subsequent call. First, we note that we could use a 2-dimension array with the previous algorithm because we only need to know about the current and previous columns. However, this will not give us enough information to get the alignment back once we find its value. We use the graph from the previous section, and define g(i,j) as the length of the shortest path from (i,j) to (m,n). In our case, we initially start at g(m,n) which is 0, and try to find g(0,0), which gives the value. We call this the Backward-Space-Efficient-Alignment, | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.8 - Shortest Paths in Graphs==== | ||
+ | |||
+ | We will denote our directed graph as G=(V,E) and give each edge a specific weight. While Dijkstra' | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.9 - Shortest Paths and Distance Vector Protocols==== | ||
+ | |||
+ | An application for Shortest Paths algorithm we used in the previous section is for a network of routers (nodes) with direct links (edges). The cost of an edge is the delay of the link and we look for a path with the shortest delay. While Dijkstra' | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.10 - Negative Cycles in a Graph==== | ||
+ | |||
+ | If we augment a graph by adding a sink node that has a path from every other node leading to it and the augmented graph has a negative cycle, then the original graph must have a negative cycle too. If we have a negative cycle and we are looking for a path from one node to the sink that passes through the cycle, as we increase the number of allowable edges, the cycle tends toward negative infinity. However, if there are no negative cycles, then opt(i, | ||
+ | |||
+ | Readability: |