[Solved]: Longest Common Subsequence Via Dynamic Programming

Problem Detail: 

I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here is correct, since the longest common subsequence of AGCAT and GAC has a length of 2:

   |A  G  C  A  T ---+-------------   G|0  1  1  1  1   A|1  1  1  2  2   C|1  1  2  2  2 

From what I understand of how it's supposed to work, the length of the LCS should appear in the bottom right cell.

But using the same method for generating the table, which you can find here, if you rearrange the letters you get an incorrect solution.

   |A  A  G  C  T ---+-------------   C|0  0  0  1  1   G|0  0  1  1  1   A|1  1  1  1  1 

Length of the LCS shouldn't have changed, the bottom right value is no longer 2.

Is my question clear enough? Am I simply following the method incorrectly? From what I understand, the order of the original sequences shouldn't matter.

Asked By : stett

Answered By : jonaprieto

Your question is clear and you are performing the method correctly, as far as see.

But it seems to be a misunderstanding about what the problem solves about strings. The longest common subsequence problem is about find out a subsequence of characters in the case of string, not necessary consecutive like substrings.

By example, some subsequences of AAGCT are: AG, AT, ACT, AGT

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37208

 Ask a Question

 Download Related Notes/Documents