Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments
type: Item
instance of: scholarly article
title: Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments
zbMATH Open document ID: 1068.60037
author: Steffen Grossmann
author: B. Yakir
published in: Bernoulli
publication date: 2005-03-30T00:00:00Z
review text: Let \(M_{mn}\) denote the optimal local gapped alignment score for two i.i.d. sequences of lengths \(m\) and \(n\) [\textit{R. Arratia} and \textit{M. S. Waterman}, Ann. Appl. Probab. 4, No. 1, 200--225 (1994; Zbl 0809.62008)]. Under very general assumptions, of the kind to be expected if local alignment is to be an appropriate tool, the authors prove that \(\lim_{m,n,t\to\infty}- t^{-1}\log P[M_{mn}> t]= \theta\), for a quantity \(\theta\) that can be determined from the model specification. They also show that \(P[M_{mn}> t]\leq cmnt^2 e^{-t\theta}\) for some \(c< \infty\) and all \(t\) large enough. This contrasts with the conjecture that \(P[M_{mn}> t]\sim Kmne^{-t\theta}\). The starting point for the argument is a theorem of \textit{J. M. Hammersley} [Ann. Probab. 2, 652--680 (1974; Zbl 0303.60044)], which establishes a large deviation estimate for the tails of an independent superadditive process.
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 2149082
reviewed by: A. D. Barbour
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3150/bj/1099579157
OpenAlex ID: W2086963976
cites work: A note on some rates of convergence in first-passage percolation
cites work: The rate of convergence of the mean length of the longest common subsequence
cites work: Approximation of subadditive functions and convergence rates in limiting-shape results
cites work: A phase transition for the score in matching random sequences allowing deletions
cites work: Critical phenomena for sequence matching with scoring
cites work: Limit distribution of maximal non-aligned two-sequence segmental score
cites work: Q5538132
cites work: Q5624436
cites work: Q3585138
cites work: Postulates for subadditive processes
cites work: Q3853400
cites work: Approximate \(p\)-values for local sequence alignments.
cites work: Q4131340
cites work: Q5691080
cites work: Sequence comparison significance and Poisson approximation
cites work: A limit theorem for matching random sequences allowing deletions
DOI: 10.3150/BJ/1099579157
description: scientific article; zbMATH DE number 2149082