Mean-Field Approximations to the Longest Common Subsequence Problem

Abstract

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 pairs 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 (Eur. Phys. J. B 7-2(1999),pp. 293-308). 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 which render the large $S$ expansion non-perturbative.

5 pages, 2 figures, remanied version, more details given in section IV

References in corpus (2)

• Extensive Simulations for Longest Common Subsequences: Finite Size Scaling, a Cavity Solution, and Configuration Space properties
• Comparing Mean Field and Euclidean Matching Problems

Cited by in corpus (6)

• Exact Asymptotic Results for a Model of Sequence Alignment
• Bethe Ansatz in the Bernoulli Matching Model of Random Sequence Alignment
• Exact solution of the Bernoulli matching model of sequence alignment
• New alphabet-dependent morphological transition in a random RNA alignment
• Unzipping of two random heteropolymers: Ground state energy and finite size effects
• A novel Recurrence-Transience transition and Tracy-Widom growth in a cellular automaton with quenched noise