Approximation to the mean curve in the LCS problem
The problem of sequence comparison via optimal alignments occurs naturally in many areas of applications. The simplest such technique is based on evaluating a score given by the length of a longest common subsequence divided by the average length of the original sequences. In this paper we investigate the expected value of this score when the input sequences are random and their length tends to infinity. The corresponding limit exists but is not known precisely. We 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 our method produces promising numerical results.
Year of publication: |
2008
|
---|---|
Authors: | Durringer, Clement ; Hauser, Raphael ; Matzinger, Heinrich |
Published in: |
Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 118.2008, 4, p. 629-648
|
Publisher: |
Elsevier |
Keywords: | Longest common subsequence problem Chvatal-Sankoff constant Steele conjecture Mean curve Large deviation theory Monte Carlo simulation Convex analysis |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Convergence of the stochastic mesh estimator for pricing Bermudan options
Avramidis, Athanassios N., (2004)
-
Convergence of the Stochastic Mesh Estimator for Pricing Bermudan Options
Matzinger, Heinrich, (2004)
-
DNA approach to scenery reconstruction
Matzinger, Heinrich, (2011)
- More ...