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 bound; Longest common subsequence; Chvatal-Sankoff conjecture

Mathematics Subject Classification ID

60K35: Interacting random processes; statistical mechanics type models; percolation theory

60C05: Combinatorial probability

41A25: Rate of convergence, degree of approximation

Related Items

Length of the Longest Common Subsequence between Overlapping Words, On the variance of the optimal alignments score for binary random words and an asymmetric scoring function, Optimal alignments of longest common subsequences and their path properties, Rate of convergence of the mean for sub-additive ergodic sequences, Thermodynamical approach to the longest common subsequence problem, 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 moments of global scores of pairwise Markov chains, Lower bounds for fluctuations in first-passage percolation for general distributions, On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions, Microscopic path structure of optimally aligned random sequences, A general method for lower bounds on fluctuations of random variables, Letter change bias and local uniqueness in optimal sequence alignments, A central limit theorem for the length of the longest common subsequences in random words, 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

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