Approximation to the mean curve in the LCS problem

DOI10.1016/J.SPA.2007.05.010MaRDI QIDQ2476294zbMATH OpenOpenAlexFDO

Authors Clement Durringer, Raphael A. Hauser, Heinrich Matzinger

Publication date 18 March 2008

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://ora.ox.ac.uk/objects/uuid:07b98b3f-6948-4014-9dc3-9552fd050896

zbMATH Keywords

convex analysislarge deviation theorylongest common subsequence problemmean curveMonte Carlo simulationSteele conjecture

Mathematics Subject Classification ID

Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Large deviations (60F10) Computational methods for problems pertaining to biology (92-08)

Review text

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.

Recommendations

• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Longest common subsequences
• An iterative approach to determining the length of the longest common subsequence of two strings
• scientific article; zbMATH DE number 13327
• scientific article; zbMATH DE number 2079331

Cites work

• A phase transition for the score in matching random sequences allowing deletions
• A Remark on Stirling's Formula
• An Efron-Stein inequality for nonsymmetric statistics
• Bounding the expected length of longest common subsequences and forests
• Convex analysis and nonlinear optimization. Theory and examples
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Large deviations
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Longest common subsequences
• Longest common subsequences of two random sequences
• Probability Inequalities for Sums of Bounded Random Variables
• Some limit results for longest common subsequences
• The rate of convergence of the mean length of the longest common subsequence
• The String-to-String Correction Problem
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Weighted sums of certain dependent random variables

Cited in

(7)

• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• Microscopic path structure of optimally aligned random sequences
• scientific article; zbMATH DE number 13327 (Why is no real title available?)
• The rate of the convergence of the mean score in random sequence comparison
• Longest common subsequences
• Thermodynamical approach to the longest common subsequence problem

This page was built for publication: Approximation to the mean curve in the LCS problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476294)