Standard deviation of the longest common subsequence

DOI10.1214/08-AOP436zbMath1182.60004arXiv0907.5137MaRDI QIDQ2270612

Heinrich III Matzinger, Jüri Lember

Publication date: 28 July 2009

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0907.5137

zbMATH Keywords

variance boundLongest common subsequenceChvatal-Sankoff conjecture

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Rate of convergence, degree of approximation (41A25)

Related Items

On the variance of the optimal alignments score for binary random words and an asymmetric scoring function, Lower bounds on the generalized central moments of the optimal alignments score of random sequences, Optimality regions and fluctuations for Bernoulli last passage models, Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets, Lower bounds for fluctuations in first-passage percolation for general distributions, Rate of convergence of the mean for sub-additive ergodic sequences, Optimal alignments of longest common subsequences and their path properties, On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words, On an alternative sequence comparison statistic of Steele, A central limit theorem for the length of the longest common subsequences in random words, Letter change bias and local uniqueness in optimal sequence alignments, Thermodynamical approach to the longest common subsequence problem, Lower bounds for moments of global scores of pairwise Markov chains, On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions, Microscopic path structure of optimally aligned random sequences, Length of the Longest Common Subsequence between Overlapping Words, A general method for lower bounds on fluctuations of random variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal alignments of longest common subsequences and their path properties
• On the longest common increasing binary subsequence
• An Efron-Stein inequality for nonsymmetric statistics
• 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
• Sequence comparison significance and Poisson approximation
• Expected length of the longest common subsequence for large alphabets
• Longest common subsequences of two random sequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment