Mean-field approximations to the longest common subsequence problem
Jacques Boutet de Monvel · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2000
The longest common subsequence (LCS) problem is a fundamental problem of sequence comparison. A natural approximation to this problem is a model in which every pair of letters of two "sequences" are matched independently of the other pairs with probability 1/S, S representing the size of the alphabet. This model is analogous to a mean-field version of the LCS problem, which can be solved with a cavity approach [J. Boutet de Monvel, Eur. Phys. J. B 7, 293 (1999)]. We refine here this approximation by incorporating in a systematic way correlations among the matches in the cavity calculation. We obtain a series of closer and closer approximations to the LCS problem, which we quantify in the large S limit, both with a perturbative approach and by Monte Carlo simulations. We find that, as it happens in the expansion around mean field for other disordered systems, the corrections to our approximations depend upon long-ranged correlation effects that render the large S expansion nonperturbative.