Conjectures

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 Subse-quence (LCS) of X and Y is a common subse-quence of X and Y of maximal length. In order to get familiar with the definition of a LCS, let us con-sider 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 obvi-ous