Approximation to the mean curve in the LCS problem (Q2476294)

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.