Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
1998-10-09
Phys. Rev. E 62-1 (2000), pp. 204-209.
Physics
Condensed Matter
Disordered Systems and Neural Networks
5 pages, 2 figures, remanied version, more details given in section IV
Scientific paper
10.1103/PhysRevE.62.204
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.
No associations
LandOfFree
Mean-Field Approximations to the Longest Common Subsequence Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Mean-Field Approximations to the Longest Common Subsequence Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mean-Field Approximations to the Longest Common Subsequence Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-259078