Thursday, January 1, 2015

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki.

Given a set of strings, how do we find the longest common sub-sequence(LCS) among them?

For example, LCS{"ATDACG","CTDACGA"} is  "TAG".

In this post, we will look at the algorithm to find the LCS of two strings. To understand the solution, let us walk through a simple example.

Let us consider the strings "ACDG", "CAG". We can recursively define the LCS of two strings str1, str2 of lengths n,m as follows.
LCS(str1, str2) = 
    LCS(str1[0:n-2], str2[0:m-2])+str1[n-1] if str1[n-1] = str2[m-1]
    Max(LCS(str1,str2[0:m-2], LCS(str1[0:n-2],str2)) otherwise

Using the above definition
LCS("ACDG","CAG") = LCS("ACD", "CA") + "G"

This means that since the last character is same, in the sub-problem we can delete it from both the strings.
Further calculations go as follows

LCS("ACD", "CA") = Max( LCS("AC", "CA"), LCS("ACD","C") )
LCS("ACD", "C") = Max( LCS("AC", "C"), LCS("ACD","") )

and so on... 

we can see that LCS("ACD","CA") is "C"; so "CG" is the final output.

If we implement this naive recursion, we repeat the calculation for many sub problems. For efficient implementation we use a 2 dimensional array of size (n+1)*(m+1).The table is calculated using the rules given below which directly follow from the recursive definition given above.
table[i][j]= 0 if either of the string is empty
           = 1 + table[i-1][j-1] if their last characters are equal
           = max(table[i-1][j], table[i][j-1]) otherwise
Here is an example table.

  ∅ B A C B A D
∅ 0 0 0 0 0 0 0
A  0 1 1 1 1 1 1
B  0 1 1 1 2 2 2
A  0 1 2 2 2 3 3
Z  0 1 2 2 2 3 3
D  0 1 2 2 2 3 4
C  0 1 2 3 3 3 4
Here are the python implementations of both approaches.