On the variance of the optimal alignments score for binary random words and an asymmetric scoring function

DOI10.1007/s10955-016-1549-1zbMath1350.60102arXivmath/0702036OpenAlexW3100974250MaRDI QIDQ330635

Christian Houdré, Heinrich III Matzinger

Publication date: 26 October 2016

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

longest common subsequencesoptimal alignmentsvariance boundsbinary random wordslast-passage percolation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Existence of optimal solutions to problems involving randomness (49J55)

Related Items (4)

Lower bounds on the generalized central moments of the optimal alignments score of random sequences ⋮ On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words ⋮ A central limit theorem for the length of the longest common subsequences in random words ⋮ A general method for lower bounds on fluctuations of random variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The rate of the convergence of the mean score in random sequence comparison
• On the longest common increasing binary subsequence
• 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
• Shape fluctuations and random matrices
• Standard deviation of the longest common subsequence
• Letter change bias and local uniqueness in optimal sequence alignments
• A central limit theorem for the length of the longest common subsequences in random words
• The Surprising Mathematics of Longest Increasing Subsequences
• On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words
• Dynamic Scaling of Growing Interfaces
• Longest common subsequences of two random sequences
• Biological Sequence Analysis
• On the distribution of the length of the longest increasing subsequence of random permutations

This page was built for publication: On the variance of the optimal alignments score for binary random words and an asymmetric scoring function