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

DOI10.1214/11-AAP778zbMATH Open1244.60095arXiv1011.2688MaRDI QIDQ433905FDOQ433905

Authors: J. Lember, Felipe Torres, Heinrich Matzinger 

Publication date: 8 July 2012

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

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.

Full work available at URL: https://arxiv.org/abs/1011.2688

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

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)

Cites Work

• Biological Sequence Analysis
• Risk bounds for model selection via penalization
• Title not available (Why is that?)
• Expected length of the longest common subsequence for large alphabets
• Approximation of subadditive functions and convergence rates in limiting-shape results
• 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
• Longest common subsequences of two random sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sequence comparison significance and Poisson approximation
• Bounding the expected length of longest common subsequences and forests
• Some limit results for longest common subsequences
• An iterative approach to determining the length of the longest common subsequence of two strings
• Approximation to the mean curve in the LCS problem
• Introduction to Computational Genomics
• Title not available (Why is that?)
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Distribution of the length of the longest common subsequence of two multi-state biological sequences

Cited In (8)

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

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)