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

DOI10.1007/S10959-016-0730-4zbMATH Open1409.60026arXiv1506.06067OpenAlexW2962749086MaRDI QIDQ1661578FDOQ1661578

Authors: Ruoting Gong, Christian Houdré, J. Lember 

Publication date: 16 August 2018

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

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.

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

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

zbMATH Keywords

longest common subsequencelast passage percolationoptimal alignment

Mathematics Subject Classification ID

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

Cites Work

• Elements of Information Theory
• Biological Sequence Analysis
• Concentration inequalities. A nonasymptotic theory of independence
• Title not available (Why is that?)
• An Efron-Stein inequality for nonsymmetric statistics
• 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
• Standard deviation of the longest common subsequence
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• Longest common subsequences of two random sequences
• Title not available (Why is that?)
• The rate of the convergence of the mean score in random sequence comparison
• Title not available (Why is that?)
• Title not available (Why is that?)
• Postulates for subadditive processes
• Introduction to Computational Genomics
• Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments
• Sparse long blocks and the micro-structure of the longuest common subsequences
• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison
• Title not available (Why is that?)

Cited In (11)

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

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)