Georgia Institute of Technology College of Sciences

We consider optimal alignments of random sequences of length n which are i.i.d. For such alignments we count which letters get aligned with which letters how often. This gives as for every opitmal alignment the frequency of the aligned letter pairs. These frequencies expressed as relative frequencies and put in vector form are called the "empirical distribution of letter pairs along an optimal alignment". It was previously established that if the scoring function is chosen at random, then the empirical distribution of letter pairs along an opitmal alignment converges. We show an upper bound for the rate of convergence which is larger thatn the rate of the alignement score. the rate of the alignemnt score can be obtained directly by Azuma-Hoeffding, but not so for the empirical distribution of the aligned letter pairs seen along an opitmal alignment: which changing on letter in one of the sequences, the optimal alginemnt score changes by at most a fixed quantity, but the empirical distribution of the aligned letter pairs potentially could change entirely.