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

2010/11/11 by Juri Lember, Lember, Juri, Heinrich Matzinger +3
Mathematics · #41A25 #60C05 #60K35 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:41A25 #msc:60C05 #msc:60K35

paper · pdf · doi:10.48550/arxiv.1011.2688

13 pages, 1 figure

arxiv created 2010/11/17 · arxiv updated 2010/11/18

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.

Related

• General approach to the fluctuations problem in random sequence comparison
• Simulations, Computations, and Statistics for Longest Common Subsequences
• Repetition-free longest common subsequence of random sequences
• An Upper Bound on the Convergence Rate of a Second Functional in Optimal Sequence Alignment
• A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words