Longest Common Subsequence

X = <x₁, x₂, x₃, ...,x_m> is a sequence

Z = <z₁, z₂, z₃, ...,z_k> is a subsequence of X if z₁ = x_i1, z₂= x_i2, ...z_k = x_ik  0 < i₁ < i₂... < i_k  £  m

Given sequences X and Y, Z is a common subsequence if Z is a subsequence to both X and Y. If Z is the longest possible subsequence of both X and Y then it is the longest common subsequence.

X = < A, G, C, G, T, A, G >

Y = < G, T, C, A, G, A >

a common subsequence is < G, C, A > also < G, C, G, A >, < G, T, A, G > and < G, C, A, G >, since no common subsequence of length 5 exists there are 3 LCS's: < G, C, G, A > , < G, T, A, G > and < G, C, A, G >.

Finding the LCS:

Could enumerate all subsequences of X (length m) ® 2^mand Y (length n) ® 2ⁿ must search for hits and sort by length. This is an exponential algorithm. LCS has an optimal substructure property based on prefixes. If X = <x₁, ...,x_m> the X_i = <x₁, ...,x_i> is the i^th prefix of X and X₀ is empty.

Theorem 16.1 ( Optimal substructure for LCS)

 If X = <x₁, ...,x_m> and  If Y = <y₁, ...,y_n> are sequences and let Z = <z₁, ...,z_k> be some LCS of X and Y.

1. If x_m =  y_n  then z_k = x_mand Z_k-1 is an LCS of X_m-1 and Y_n-1

2. If x_m ¹ y_n  then z_k ¹x_m Þ Z is an LCS of X_m-1 and Y

3. If x_m ¹ y_n  then z_k ¹y_n Þ Z is an LCS of X and Y _n-1

Proof:

1. If z_k ¹x_m then we could add x_m =  y_n to Z to get an LCS of length k + 1. By contradiction it must be that z_k = x_m =  y_n . |z_k-1 | = k - 1 and is an LCS of  X_m-1 and Y_n-1 . It is an LCS, if not then $ W CS of X_m-1 and Y_n-1 with | W | > k - 1 and so by appending x_m =  y_n we get a CS of X  and Y of length greater than k, a contradiction.

2. If z_k ¹x_m then z is a CS of X_m-1 and Y. If  $ W a CS with | W | > k, then W would be a CS of X and Y, a contradiction

3. Proof by reversing x and y

This means that to find the LCS of X and Y:

if x_m =  y_n find LCS of and

If   x_m ¹ y_n

1. find LCS of X_m-1and Y

2. find LCS of X and Y_n-1

and take the larger of 'a.' or 'b.'. Thus we start with small problem, find LCS and grow our solution:

Let c[i, j] = | W |, W is LCS of X_i and Y_j

c[i, j] = 0                     if i*j = 0

         = c[i-1,j-1] + 1,                 if i*j > 0 and x_i = y_j

         = max (c[i, j-1]. c[i-1, j])    if i,j > 0 and  x_i ¹ y_j

Could use this to write an exponential algorithm via recursion. However, there are only Q (m n) sub-problems, so we use DP. Store c[i, j] and b[i, j] which points to the optimal sub-problem chosen. c[m, n] contains the length of the LCS and b[m, n] directions used to build it.

LCS-Length ( X, Y )

1. m ¬ length[X]

2. n ¬ length[Y]

3. for i ¬ 1 to m

4.    do c[i,0] ¬ 0

5. for j ¬ 0 to n

6.    do c[0, j] ¬ 0

7. for i ¬ 1 to m

8.    do for j ¬ 1 to n

9.       do if  x_i = y_j

10.             then c[i, j] ¬ c[i-1, j-1] + 1

11.                     b[i, j] ¬ "\"

12.             else if c[i - 1, j] ³ c[i, j-1]

13.                then c[i, j] ¬ c[i-1, j]

14.                        b[i, j] ¬ "Ý"

15.                else c[i, j] ¬ c[i, j-1]

16.                       b[i,j] ¬ "¬"

17. return c and b

Running Time = O (m n) since each table entry takes O (1) time.

Note:

"\" means both the same

"Ý" means c[i - 1, j] ³ c[i, j-1]

"¬" means c[i - 1, j] < c[i, j-1]

The "\" diagonal arrows lengthen the LCS

Print-LCS (b, X, i, j)

1. If i = 0 or j = 0

2.    then return

3. if b[i,j] = "\"

4.    then Print-LCS (b, X, i-1, j-1)

5.       print x_i

6. else if b[i,j] = "Ý"

7.    then Print-LCS ( b, X, i-1, j)

8. else Print-LCS (b, X, i, j-1)

This takes O ( m + n ) since either i or j is decremented in the recursion.