4. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
5. Tracing Back in the LCS Algorithm
6. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
7. Tracing Back in the LCS Algorithm
8. ** after Chapter7.ppt
9. Tracing Back in the LCS Algorithm
10. ** after Chapter7.ppt
11. Fibonacci Sequence
12. Dynamic Programming
13. The Shortest Path
14. The Shortest Path in Multi-stage Graphs
15. Dynamic Programming Approach
16. d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called
17. Backward Approach (Forward Reasoning)
18. Slide 9
19. Principle of Optimality
20. Dynamic Programming
21. The Resource Allocation Problem
22. The Multi-Stage Graph Solution
23. The Resource Allocation Problem
24. The Multi-Stage Graph Solution
25. Slide 14
26. The Longest Common Subsequence (LCS) problem
27. The LCS Algorithm
28. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
29. Tracing Back in the LCS Algorithm
30. The Two-Sequence Alignment Problem
31. Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.
32. Let Ai,j denote the optimal alignment score between a1 a2 ai and b1 b2 bj and, where 1 i m and 1 j n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2 ai are all aligned with “-”. A0,j : b1 b2 bj are all aligned with “-”.f(ai ,-): ai is al
33. The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:
34. In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the
35. Edit Distance
36. For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of
37. Slide 26
38. The RNA Maximum Base Pair Matching Problem
39. E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:
40. An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1 i < j n.(1) j - i > t, where t is a small positive constant. Typically, t =
41. Dynamic Programming
42. To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.
43. Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.
44. Case 3: In the optimal solution, rj is paired with some rk, where i + 1 k j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.
45. Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then
97. Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then
98. Case 3: In the optimal solution, rj is paired with some rk, where i + 1 k j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.
99. Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.
100. To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.
101. Dynamic Programming
102. An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1 i < j n.(1) j - i > t, where t is a small positive constant. Typically, t =
103. E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:
104. The RNA Maximum Base Pair Matching Problem
105. Slide 26
106. For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of
107. Edit Distance
108. In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the
109. The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:
110. Let Ai,j denote the optimal alignment score between a1 a2 ai and b1 b2 bj and, where 1 i m and 1 j n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2 ai are all aligned with “-”. A0,j : b1 b2 bj are all aligned with “-”.f(ai ,-): ai is al
111. Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.
112. The Two-Sequence Alignment Problem
113. Tracing Back in the LCS Algorithm
114. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
115. The LCS Algorithm
116. The Longest Common Subsequence (LCS) problem
117. Slide 14
118. The Multi-Stage Graph Solution
119. The Resource Allocation Problem
120. Dynamic Programming
121. Principle of Optimality
122. Slide 9
123. Backward Approach (Forward Reasoning)
124. d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called
Prev