Summation test for gap penalties and strong law of the local alignment score (Q558686)

The author studies a situation, which typically occurs in the problem of DNA sequence matching. Two sequences of length \(m\) and \(n\) are aligned to determine whether they have a segment each, that is significantly matched. The author defines a local alignment score \(H\) and a global alignment score \(G\), which measure the quality of the matches in the alignment subtracted by penalties for gaps present within the alignment. The gap penalty is assumed to be a nondecreasing concave function of the form \(g(k) = \Delta + \gamma(k)\), where \(\Delta\) is a constant, which reflects the belief in the frequency of segment insertion/deletion in the evolutionary process. The local assignment score \(H\) defined by the author generalizes the local alignment score for gap less alignments \(H_\infty\) which was studied by \textit{A. Dembo, S. Karlin, O. Zeitouni} [Ann. Probab. 22, No. 4, 1993--2021 (1994; Zbl 0834.60031); Ann. Probab. 22, No. 4, 2022--2039 (1994; Zbl 0836.60023)]. Extending results obtained by \textit{R. Arratia} and {M. S. Waterman} [Ann. Appl. Probab. 4, 200--225 (1994; Zbl 0809.62008)], \textit{Y. Zhang} [Ann. Appl. Probab. 5, 1236--1240 (1995; Zbl 0855.62012)] as well as those of Dembo et al. (op. cit.), the author obtains various results about asymptotic properties of \(H\) and \(G\).