Extensive simulations for longest common subsequences

Given two strings X and Y of N and M characters respectively, the Longest Common Subsequence (LCS) Problem asks for the longest sequence of (non-contiguous) matches between X and Y. Using extensive Monte-Carlo simulations for this problem, we find a finite size scaling law of the form $E(L_N)/N =\gamma_S + A_S/(\ln{N\sqrt{N}})+...$ for the average LCS length of two random strings of size N over S letters. We provide precise estimates of $\gamma_S$ for $2\le S\le 15$. We consider also a related Bernoulli Matching model where the different entries of an $N\times M$ array are occupied with a match independently with probability 1/S. On the basis of a cavity-like analysis we find that the length of a longest sequence of matches in that case behaves as $L_{NM}^B\sim \gamma^B_S(r) N$ where r=M/N and $\gamma^B_S(r)=(2\sqrt{rS}-r-1)/(S-1)$. This formula agrees very well with our numerical computations. It provides a very good approximation for the Random String model, the approximation getting more accurate as S increases. The question of the "universality class" of the LCS problem is also considered. Our results for the Bernoulli Matching model show very good agreement with the scaling predictions of [CITE] for Needleman-Wunsch sequence alignment. We find however that the variance of the LCS length has a scaling different from Var$(L_N)\approx N^{2/3}$ in the Random String model, suggesting that long-ranged correlations among the matches are relevant in this model. We finally study the "ground state" properties of this problem. We find that the number ${\mathcal N}_{LCS}$ of solutions typically grows exponentially with N. In other words, this system does not satisfy "Nernst's principle" . This is also reflected at the level of the overlap between two LCSs chosen at random, which is found to be self averaging and to approach a definite value $q_S< 1$ as $N\to \infty$