Large deviations for optimal local alignment scores of independent sequences

The distribution function of the optimal local gapped alignment

score of two

long unrelated DNA sequences of length n is widely believed to be

of the Gumbel type

. Whereas this is well known

for gapless alignment

(Dembo et al., 1994), a rigorous justification of this belief in the

gapped case has only been given in special cases (e.g. Siegmund/Yakir, 2000).

The two parameters K and of course depend on the scoring scheme,

but numerically useable representations are available in these cases.

We look at

in the large

deviations regime, that is where . We give a connection

between this large deviations rate and the growth constant of the

expectation of in the logarithmic regime (Arratia/Waterman,

1994). We also provide a new representation for this limit via a characteristic

equation for moment-generating functions of optimal global

alignment scores. This representation is similar to the one known

from gapless alignment.

Assuming the correctness of the Gumbel form, this gives a new representation

for the parameter .