Large deviations-based upper bounds on the expected relative length of longest common subsequences

DOI10.1239/aap/1158685004zbMath1101.60016OpenAlexW1988706090MaRDI QIDQ5395363

Raphael Hauser, Servet Martínez, Heinrich III Matzinger

Publication date: 2 November 2006

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1239/aap/1158685004

zbMATH Keywords

upper boundMonte Carlo simulationlongest common subsequence problemlarge deviation theoryChvátal-Sankoff constant

Mathematics Subject Classification ID

Large deviations (60F10) Asymptotic enumeration (05A16) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Related Items

Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets ⋮ 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 ⋮ Approximation to the mean curve in the LCS problem ⋮ Standard deviation of the longest common subsequence ⋮ Microscopic path structure of optimally aligned random sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• General methods of sequence comparison
• Ergodic theorems. With a supplement by Antoine Brunel
• An Efron-Stein inequality for nonsymmetric statistics
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Some limit results for longest common subsequences
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• 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
• A Poisson approximation for sequence comparisons with insertions and deletions
• Weighted sums of certain dependent random variables
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Sequences
• Longest common subsequences of two random sequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• The String-to-String Correction Problem
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Probability Inequalities for Sums of Bounded Random Variables
• LATIN 2004: Theoretical Informatics

This page was built for publication: Large deviations-based upper bounds on the expected relative length of longest common subsequences