Lower bounds on the generalized central moments of the optimal alignments score of random sequences

DOI10.1007/S10959-016-0730-4MaRDI QIDQ1661578zbMATH OpenOpenAlexFDO

Authors Ruoting Gong, Christian Houdré, J. Lember

Publication date 16 August 2018

Published in Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

longest common subsequencelast passage percolationoptimal alignment

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Large deviations (60F10) Combinatorial probability (60C05)

Abstract: We present a general approach to the problem of determining tight asymptotic lower bounds for generalized central moments of the optimal alignment score of two independent sequences of i.i.d. random variables. At first, these are obtained under a main assumption for which sufficient conditions are provided. When the main assumption fails, we nevertheless develop a "uniform approximation" method leading to asymptotic lower bounds. Our general results are then applied to the length of the longest common subsequence of binary strings, in which case asymptotic lower bounds are obtained for the moments and the exponential moments of the optimal score. As a byproduct, a local upper bound on the rate function associated with the length of the longest common subsequences of two binary strings is also obtained.

Recommendations

• Lower bounds for optimal alignments of binary sequences
• scientific article; zbMATH DE number 5226755
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• An upper bound on the convergence rate of a second functional in optimal sequence alignment
• Order of the fluctuation for the LCS and optimal alignment score of binary sequences when the rescaled expectation is not constant
• Upper bounds and importance sampling of \(p\)-values of DNA and protein sequence alignments
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function

Cites work

• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 835835 (Why is no real title available?)
• scientific article; zbMATH DE number 5873671 (Why is no real title available?)
• scientific article; zbMATH DE number 5205668 (Why is no real title available?)
• A phase transition for the score in matching random sequences allowing deletions
• An Efron-Stein inequality for nonsymmetric statistics
• Biological Sequence Analysis
• Concentration inequalities. A nonasymptotic theory of independence
• Elements of Information Theory
• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• Introduction to Computational Genomics
• Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments
• Longest common subsequences of two random sequences
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• Postulates for subadditive processes
• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison
• Sparse long blocks and the micro-structure of the longuest common subsequences
• Standard deviation of the longest common subsequence
• The rate of convergence of the mean length of the longest common subsequence
• The rate of the convergence of the mean score in random sequence comparison

Cited in

(11)

• Microscopic path structure of optimally aligned random sequences
• Inequalities for the score constant in matching random sequences
• Closeness to the diagonal for longest common subsequences in random words
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• The rate of the convergence of the mean score in random sequence comparison
• Lower bounds for moments of global scores of pairwise Markov chains
• Lower bounds for fluctuations in first-passage percolation for general distributions
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• A Monte Carlo approach to the fluctuation problem in optimal alignments of random strings
• Order of the fluctuation for the LCS and optimal alignment score of binary sequences when the rescaled expectation is not constant
• A general method for lower bounds on fluctuations of random variables

This page was built for publication: Lower bounds on the generalized central moments of the optimal alignments score of random sequences

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