Closeness to the diagonal for longest common subsequences in random words

DOI10.1214/16-ECP4029MaRDI QIDQ287834zbMATH OpenOpenAlexFDO

Authors Christian Houdré, Heinrich Matzinger

Publication date 23 May 2016

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.2031, https://projecteuclid.org/euclid.ecp/1461781966

zbMATH Keywords

edit/Levensthein distancelast passage percolationlongest common subsequencesoptimal alignments

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Large deviations (60F10)

Abstract: The nature of the alignment with gaps corresponding to a longest common subsequence (LCS) of two independent iid random sequences drawn from a finite alphabet is investigated. It is shown that such an optimal alignment typically matches pieces of similar short-length. This is of importance in understanding the structure of optimal alignments of two sequences. Moreover, it is also shown that any property, common to two subsequences, typically holds in most parts of the optimal alignment whenever this same property holds, with high probability, for strings of similar short-length. Our results should, in particular, prove useful for simulations since they imply that the re-scaled two dimensional representation of a LCS gets uniformly close to the diagonal as the length of the sequences grows without bound.

Recommendations

• Optimal alignments of longest common subsequences and their path properties
• Sparse long blocks and the micro-structure of the longuest common subsequences
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• The rate of convergence of the mean length of the longest common subsequence

Cited in

(8)

• Optimality regions and fluctuations for Bernoulli last passage models
• Longest common substring for random subshifts of finite type
• Periodic words, common subsequences and frogs
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• A central limit theorem for the length of the longest common subsequences in random words
• Optimal alignments of longest common subsequences and their path properties
• Order of the fluctuation for the LCS and optimal alignment score of binary sequences when the rescaled expectation is not constant
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment

This page was built for publication: Closeness to the diagonal for longest common subsequences in random words

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