The rate of the convergence of the mean score in random sequence comparison

DOI10.1214/11-AAP778MaRDI QIDQ433905zbMATH OpenFDO

Authors J. Lember, Felipe Torres, Heinrich Matzinger

Publication date 8 July 2012

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

Full work available at URL https://arxiv.org/abs/1011.2688, https://projecteuclid.org/euclid.aoap/1337347538

zbMATH Keywords

rate of convergencelongest common sequencerandom sequence comparison

Mathematics Subject Classification ID

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

Abstract: We consider a general class of super-additive scores measuring the similarity of two independent sequences of $n$ i.i.d. letters from a finite alphabet. Our object of interest is the mean score by letter $l_n$. By the subadditivity $l_n$ is nondecreasing and converges to a limit $l$. We give a simple method of bounding the difference $l-l_n$ and obtaining the rate of convergence. Our result generalizes a previous result of Alexander, where only the special case of the longest common subsequence is considered.

Recommendations

• The rate of convergence of the mean length of the longest common subsequence
• Stochastic scrabble: large deviations for sequences with scores
• Approximation to the mean curve in the LCS problem
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• Critical phenomena for sequence matching with scoring

Cites work

• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 2079331 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• A phase transition for the score in matching random sequences allowing deletions
• An iterative approach to determining the length of the longest common subsequence of two strings
• Approximation of subadditive functions and convergence rates in limiting-shape results
• Approximation to the mean curve in the LCS problem
• Biological Sequence Analysis
• Bounding the expected length of longest common subsequences and forests
• Distribution of the length of the longest common subsequence of two multi-state biological sequences
• Expected length of the longest common subsequence for large alphabets
• Introduction to Computational Genomics
• Longest common subsequences of two random sequences
• Risk bounds for model selection via penalization
• Sequence comparison significance and Poisson approximation
• Some limit results for longest common subsequences
• The rate of convergence of the mean length of the longest common subsequence
• Upper bounds for the expected length of a longest common subsequence of two binary sequences

Cited in

(8)

• On the rate of convergence for the length of the longest common subsequences in hidden Markov models
• On rates of convergence for common subsequences and first passage time
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• scientific article; zbMATH DE number 434722 (Why is no real title available?)
• An upper bound on the convergence rate of a second functional in optimal sequence alignment
• Optimal alignments of longest common subsequences and their path properties
• Lower bounds for moments of global scores of pairwise Markov chains
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function

This page was built for publication: The rate of the convergence of the mean score in random sequence comparison

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433905)