Preprint D16/2006
Approximation to the Mean Curve in the LCS Problem

Heinrich Matzinger | Durringer, Clement | Hauser, Raphael

**Keywords: **
Longest common subsequence problem | Chvatal-Sankoff constant | Steele conjecture | large deviation theory | convex analysis

The problem of sequence comparison via optimal alignments occurs
naturally in many areas of applications. The simplest such technique
is based on evaluating a score given by the length of a longest
common subsequence divided by the average length of the original
sequences. In this paper we investigate the expected value of this
score when the input sequences are random and their length tends
to infinity. The corresponding limit exists but is not known precisely.
We derive a large-deviation, convex analysis and Montecarlo based
method to compute a consistent sequence of upper bounds on the
unknown limit.