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 > and < G, T, A, A > since no common subsequence of length 5 exists there are 2 LCG's: < G, C, G, A > and < G, T, 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> then 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, 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_m Þ 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 X_m-1 and Y_m-1

If   x_m ¹ y

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
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.