Approximation to the mean curve in the LCS problem (Q2476294)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation to the mean curve in the LCS problem |
scientific article |
Statements
Approximation to the mean curve in the LCS problem (English)
0 references
18 March 2008
0 references
This paper contains an analysis of the problem of sequence comparison via alignments. A family of sophisticated methods is based on looking at subsequences of the original strings and their likely descendants under a mutation process based on a hidden Markov model. The simplest method of this kind is to measure the similarity between strings by the relative length of longest common subsequence (LCS) with respect to the mean of the lengths of the original sequences. A subsequence of a string is defined as any string obtained by deleting some of the characters from the original string and keeping the remaining characters in the same order. In this article the authors study the asymptotic expectation of the LCS method. The corresponding limit exists but is not known precisely. They derive a theoretical large deviation, convex analysis and Monte Carlo based method to compute a consistent sequence of upper bounds on the unknown limit. An empirical practical version of method produces promising numerical results.
0 references
longest common subsequence problem
0 references
Steele conjecture
0 references
mean curve
0 references
large deviation theory
0 references
Monte Carlo simulation
0 references
convex analysis
0 references
0 references
0 references