Symmetry and Fractal-like Structures in the Statistics of Sequence Comparison

One of the oustanding open problems at the heart of gapped sequence alignment is the longest common subsequence (LCS) problem which is stated as follows: given two random sequences (in a finite alphabet) of length N, what is the longest common subsequence shared by the two sequences? Although the expected value and variance of the distribution are known to lie within certain limits, their exact values and the exact distribution over all possible length subsequences k, 0 ≤ k ≤ N, for all sequence lengths N are unknown. In the simplest version of the problem, the sequences are chosen randomly from a binary alphabet. The distributions generated in the binary case can be generalized to other finite alphabets. For low values of N we look at all possible sequences of length N and calculate the LCS for all pairs. An iterative approach is then introduced which assists in determining the alignments whose scores increased by one upon the addition of one letter to each sequence. Those sequence pairs whose score did increase are shown on an array, which has a remarkable fractal-like structure. As the sequence length increases, the area of the fractal approaches the Chvátal-Sankoff constant ac (the proportionality constant for the linear growth of the expected length of the LCS with sequence length). We show that the iterative value in fact converges more rapidly to ac. The exact value of this constant is as yet unknown