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

DOI10.1007/S10955-016-1549-1zbMATH Open1350.60102arXivmath/0702036OpenAlexW3100974250MaRDI QIDQ330635FDOQ330635

Christian Houdré, Heinrich Matzinger

Publication date: 26 October 2016

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

Abstract: We investigate the order of the variance of the optimal alignments score of two independent iid binary random words having the same length. The letters are equiprobable, but the scoring function is such that one letter has a larger score than the other. In this setting, we prove that the order of variance is linear in the common length. Optimal alignments constitute a generalization of longest common subsequences, they can be represented as optimal paths in a two-dimensional last passage percolation setting with dependent weights.

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

Recommendations

• Order of the fluctuation for the LCS and optimal alignment score of binary sequences when the rescaled expectation is not constant
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• Optimal alignments of longest common subsequences and their path properties

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)

Cites Work

• Biological Sequence Analysis
• Shape fluctuations and random matrices
• Dynamic Scaling of Growing Interfaces
• On the distribution of the length of the longest increasing subsequence of random permutations
• An Efron-Stein inequality for nonsymmetric statistics
• The Surprising Mathematics of Longest Increasing Subsequences
• 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
• 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
• On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words
• 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the longest common increasing binary subsequence

Cited In (6)

• A central limit theorem for the length of the longest common subsequences in random words
• On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words
• Scoring unusual words with varying mismatch errors
• A general method for lower bounds on fluctuations of random variables
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison

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

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