 Approximation to the mean curve in the LCS problemClement Durringer, Raphael Hauser and Heinrich Matzinger Stochastic Processes and their Applications, 2008, vol. 118, issue 4, 629-648 Abstract: 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. Keywords: Longest; common; subsequence; problem; Chvatal-Sankoff; constant; Steele; conjecture; Mean; curve; Large; deviation; theory; Monte; Carlo; simulation; Convex; analysis (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:118:y:2008:i:4:p:629-648 Ordering information: This journal article can be ordered from Access Statistics for this article Stochastic Processes and their Applications is currently edited by T. Mikosch More articles in Stochastic Processes and their Applications from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.