In computational genetics and computational linguistics, one of the basic problems is to find an optimal alignment between two given sequences (texts), X and Y. This requires a scoring system which can rank the alignments. Typically a substitution matrix gives the score for each possible pair of letters. The total score of an alignment is the sum of terms for each aligned pair of residues, plus terms for each gap. Sometimes we consider the special case where the substitution matrix is equal to the identity matrix and the gap-penalty is zero. In this case, the optimal score is equal to the length of the Longest Common Subsequence (LCS) of the two texts X and Y. (A common subsequence of X and Y is a sequence which is a subsequence of X as well as of Y). We frequently refer to the length of the LCS of X and Y as the optimal LCS-score.


A long open standing problem in the LCS context is to determine the exact order of the fluctuation of the LCS length. For this we take the text X and Y to be i.i.d. and independent of each other. We solved the long open problem of the order of the fluctuation of the LCS and the OA in several important cases. Here are some of our results:

Expected value

One of the main ideas which allowed all the subsequent developements is contained in: Large deviation approach to LCS. The idea is to identify each alignment with an increasing sequence of stopping times. Then, one tries to figure out a low-entropy class of stopping times which is likely to contain the OA. The rest is large deviation in order to control what happens along the alignments from the class. With this approach we beat the existing bounds for the LCS-constant. The same technique is applied to the LCS curve in: The expected curve.

Structure of the optimal alignment path

We developed a set of techniques which yield results on the microscopical and macroscopical structure of the optimal path, as well as the transversal and longitudinal fluctuations. Furthermore, we discovered deep relations between these entities. Some of these results are contained in: