Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments (Q1769784)

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.