Longest Common Subsequence Problem for Sequences of Independent Blocks

Let X and Y be two finite strings over a finite alphabet Σ. A common subsequence of X and Y is a subsequence which is a subsequence of X as well as of Y . A Longest Common Subsequence (LCS) of X and Y is a common subsequence of X and Y of maximal length. In order to get familiar with the definition of a LCS, let us consider the DNA-alphabet Σ = {A,G,C, T}. Let us consider two sequences x = ACGTAGCA and y = ACCGTATA. If we compare them letter by letter the great similarity does not become obvious: x A C G T A G T A