The longest common subsequence (LCS) of two
sequences is...well...best described by an example.
First, take two
strings:
apple
pale
Now, what is the longest sequence of characters common to both strings? Note here the technical
difference between a
string (no gaps) and a
sequence (any gaps). The solution for this ultra-simple puzzle is :
apple
pale
LCS(apple, pale) = ale
This can be done for any pair of sequences by
dynamic programming, and is related to the concept of
edit distance. However, there is a minor problem with LCS :
pale
apple
LCS(pale, apple) = ple
If there are two or more subsequences of indentical length, it is difficult to know which is 'better'. This potentially makes it harder to use for comparing
more than two sequences. The
reason for using this technique is for things like
local sequence alignment in
bioinformatics. So multiple alignments have to use some sort of
heuristic to choose which ones to compare first.