22+2 2345 233 2 4566 Running time and memory: O(mn)and O(mn) Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-15
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-15 i j 0 1 p 2 r 3 o 4 v 5 i 6 d 7 e 8 n 9 c 10 e 0 0 0 0 0 0 0 0 0 0 0 0 1 p 2 0 1 1 1 1 1 1 1 1 1 1 2 r 0 1 2 2 2 2 2 2 2 2 2 3 e 0 1 2 2 2 2 2 3 3 3 3 4 s 0 1 2 2 2 2 2 3 3 3 3 5 i 0 1 2 2 2 3 3 3 3 3 3 6 d 0 1 2 2 2 3 4 4 4 4 4 7 e 0 1 2 2 2 3 4 5 5 5 5 8 n 0 1 2 2 2 3 4 5 6 6 6 9 t 0 1 2 2 2 3 4 5 6 6 6 Running time and memory: O(mn) and O(mn)
The backtracing algorithm procedure Output-LCS(A, prev, i, j) I if i=0 orj=0 then return Output- LCS(A, prev, i-l,j-D) 2 if prev,j=”K“then print a 3 else if prev(,∥=?↑“ then Output-LCS(.,pren,i-l,j 4 else Output-LCSY(A, prev, i,j-1) Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-16
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-16 procedure Output-LCS(A, prev, i, j) 1 if i = 0 or j = 0 then return 2 if prev(i, j)=” “ then − − − ai Output LCS A prev i j print ( , , 1, 1) 3 else if prev(i, j)=” “ then Output-LCS(A, prev, i-1, j) 4 else Output-LCS(A, prev, i, j-1) The backtracing algorithm
222 2333 2333 444 9t 566 Output riden Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-17
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-17 i j 0 1 p 2 r 3 o 4 v 5 i 6 d 7 e 8 n 9 c 10 e 0 0 0 0 0 0 0 0 0 0 0 0 1 p 2 0 1 1 1 1 1 1 1 1 1 1 2 r 0 1 2 2 2 2 2 2 2 2 2 3 e 0 1 2 2 2 2 2 3 3 3 3 4 s 0 1 2 2 2 2 2 3 3 3 3 5 i 0 1 2 2 2 3 3 3 3 3 3 6 d 0 1 2 2 2 3 4 4 4 4 4 7 e 0 1 2 2 2 3 4 5 5 5 5 8 n 0 1 2 2 2 3 4 5 6 6 6 9 t 0 1 2 2 2 3 4 5 6 6 6 Output: priden
The backtracing algorithn procedure Output-LCS(A, prev, i, j) I if i=0 orj=0 then return Output- LCS(A, prev, i-l,j-D) 2 if prev,j=”K“then print a 3 else if prev(,∥=?↑“ then Output-LCS(.,pren,i-l,j 4 else Output-LCSY(A, prev, i,j-1) Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-18
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-18 procedure Output-LCS(A, prev, i, j) 1 if i = 0 or j = 0 then return 2 if prev(i, j)=” “ then − − − ai Output LCS A prev i j print ( , , 1, 1) 3 else if prev(i, j)=” “ then Output-LCS(A, prev, i-1, j) 4 else Output-LCS(A, prev, i, j-1) The backtracing algorithm
Pairwise Alignment Sequence A: CTTAACT Sequence B: CGGaTCaT An alignment ofa and b: TTAACT Sequence A CGGATCA--T Se equence B Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-19
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-19 C---TTAACT CGGATCA--T Pairwise Alignment Sequence A: CTTAACT Sequence B: CGGATCAT An alignment of A and B: Sequence A Sequence B