Approximation to the mean curve in the LCS problem

DOI10.1016/j.spa.2007.05.010zbMath1140.60014OpenAlexW2050733128MaRDI QIDQ2476294

Heinrich III Matzinger, Clement Durringer, Raphael Hauser

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

Monte Carlo simulationconvex analysislongest common subsequence problemlarge deviation theorymean curveSteele conjecture

Mathematics Subject Classification ID

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

Related Items

Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets ⋮ The rate of the convergence of the mean score in random sequence comparison ⋮ Thermodynamical approach to the longest common subsequence problem ⋮ On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions ⋮ Microscopic path structure of optimally aligned random sequences

Cites Work

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

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