Large deviations-based upper bounds on the expected relative length of longest common subsequences
From MaRDI portal
Publication:5395363
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
upper boundMonte Carlo simulationlongest common subsequence problemlarge deviation theoryChvátal-Sankoff constant
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