A phase transition for the score in matching random sequences allowing deletions

DOI10.1214/aoap/1177005208zbMath0809.62008OpenAlexW2041976742MaRDI QIDQ1327613

Michael S. Waterman, Richard Arratia

Publication date: 2 April 1995

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

Full work available at URL: https://doi.org/10.1214/aoap/1177005208

zbMATH Keywords

percolationphase transitionlogarithmic growthlarge deviationsprotein sequencesDNAstring matchinglinear growthlongest common subsequencemismatchesdeletionsAzuma-Hoeffdingblock deletion penaltiesbounded increments martingale methodcontiguous subsequencesgeneral letter-to-letter alignment penaltiesLipschitz functionals of marked processesoptional alignment scorerewarding matchessequence matching problem

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Applications of statistics to biology and medical sciences; meta analysis (62P10) Applications of statistics (62P99)

Related Items (26)

Greedy lattice animals: Negative values and unconstrained maxima ⋮ Approximation of subadditive functions and convergence rates in limiting-shape results ⋮ On the variance of the optimal alignments score for binary random words and an asymmetric scoring function ⋮ Lower bounds on the generalized central moments of the optimal alignments score of random sequences ⋮ Increasing sequences of independent points on the planar lattice ⋮ Optimal alignments of longest common subsequences and their path properties ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ The rate of the convergence of the mean score in random sequence comparison ⋮ On the shortest distance between orbits and the longest common substring problem ⋮ Letter change bias and local uniqueness in optimal sequence alignments ⋮ Thermodynamical approach to the longest common subsequence problem ⋮ Large deviations-based upper bounds on the expected relative length of longest common subsequences ⋮ A phase transition for the minimum free energy of secondary structures of a random RNA ⋮ Approximation to the mean curve in the LCS problem ⋮ Exact distribution of the local score for Markovian sequences ⋮ Path reversal, islands, and the gapped alignment of random sequences ⋮ Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments ⋮ Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment ⋮ Summation test for gap penalties and strong law of the local alignment score ⋮ Standard deviation of the longest common subsequence ⋮ On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions ⋮ An improved approximation for assessing the statistical significance of molecular sequence features ⋮ Longest common substring for random subshifts of finite type ⋮ Estimating the Gumbel scale parameter for local alignment of random sequences by importance sampling with stopping times ⋮ An analytic study of the phase transition line in local sequence alignment with gaps ⋮ The asymptotics of waiting times between stationary processes, allowing distortion

This page was built for publication: A phase transition for the score in matching random sequences allowing deletions