A Statistical Theory of Sequence Alignment with Gaps

Proceedings Of The Sixth International Conference On Intelligent Systems For Molecular Biology

Volume

Proceedings Of The Sixth International Conference On Intelligent Systems For Molecular Biology

Contents

A statistical theory of local alignment algorithms with gaps is presented. Both the linear and logarithmic phases, as well as the phase transition separating the two phases, are described in a quantitative way. Markov sequences without mutual correlations are shown to have scale-invariant alignment statistics. Deviations from scale invariance indicate the presence of mutual correlations detectable by alignment algorithms. Conditions are obtained for the optimal detection of a class of mutual sequence correlations.