A Limit Theorem for Matching Random Sequences Allowing Deletions

We consider a sequence matching problem involving the optimal alignment score for contiguous sequences, rewarding matches by one unit and penalizing for deletions and mismatches by parameters . and ., respectively. Let Mn be the optimal score over all possible choices of two contiguous regions. Arratia and Waterman conjectured that, when the score constant a(.,.)<0, P(Mnlogn.2b)=1 for some constant b. Here we prove the conjecture affirmatively.