- Series
- Stochastics Seminar
- Time
- Thursday, October 3, 2013 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Henry Matzinger – GaTech
- Organizer
- Ionel Popescu
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.