Large deviations-based upper bounds on the expected relative length of longest common subsequences
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 2079331
- Improved bounds on the average length of longest common subsequences
- The rate of convergence of the mean length of the longest common subsequence
- Bounding the expected length of longest common subsequences and forests
- Upper bounds for the expected length of a longest common subsequence of two binary sequences
Cites work
- A phase transition for the score in matching random sequences allowing deletions
- A Poisson approximation for sequence comparisons with insertions and deletions
- An Efron-Stein inequality for nonsymmetric statistics
- An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
- Bounding the expected length of longest common subsequences and forests
- Ergodic theorems. With a supplement by Antoine Brunel
- General methods of sequence comparison
- scientific article; zbMATH DE number 699389 (Why is no real title available?)
- scientific article; zbMATH DE number 722098 (Why is no real title available?)
- scientific article; zbMATH DE number 1516705 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Longest common subsequences of two random sequences
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- On the distribution of the length of the longest increasing subsequence of random permutations
- Probability Inequalities for Sums of Bounded Random Variables
- Sequence comparison significance and Poisson approximation
- Sequences
- Some limit results for longest common subsequences
- The Erdős-Rényi law in distribution, for coin tossing and sequence matching
- The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
- The rate of convergence of the mean length of the longest common subsequence
- The String-to-String Correction Problem
- Two moments suffice for Poisson approximations: The Chen-Stein method
- Upper bounds for the expected length of a longest common subsequence of two binary sequences
- Weighted sums of certain dependent random variables
Cited in
(21)- Bounding the expected length of longest common subsequences and forests
- The rate of convergence of the mean length of the longest common subsequence
- String matching bounds via coding
- Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
- Lower bounds for moments of global scores of pairwise Markov chains
- An iterative approach to determining the length of the longest common subsequence of two strings
- Sparse long blocks and the micro-structure of the longuest common subsequences
- Standard deviation of the longest common subsequence
- Microscopic path structure of optimally aligned random sequences
- Letter change bias and local uniqueness in optimal sequence alignments
- Approximation to the mean curve in the LCS problem
- Expected length of the longest common subsequence for large alphabets
- Improved bounds on the average length of longest common subsequences
- scientific article; zbMATH DE number 2079331 (Why is no real title available?)
- Upper bounds for the expected length of a longest common subsequence of two binary sequences
- On the convergence of upperbBound techniques for the average length of longest common subsequences
- On the rate of convergence for the length of the longest common subsequences in hidden Markov models
- scientific article; zbMATH DE number 5873671 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
- Thermodynamical approach to the longest common subsequence problem
This page was built for publication: Large deviations-based upper bounds on the expected relative length of longest common subsequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395363)
