Longest Common Subsequence Via Dynamic Programming

Question

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.

Answer 1

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

• stett: Ah - I see. I suppose I was reading subsequence to mean subset, as in order of the letters doesn't matter. I see now that the order matters for subsets, but adjacency doesn't. Thanks.
• stett: ack - I meant "... order matters for subsequences, but adjacency doesnt".