A statistical theory of sequence alignment with gaps.
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.
Max-Planck-Institut für Kolloid- und Grenzflächenforschung, Teltow, Germany. drasdo@imise.uni-leipzig.de
D
D
Drasdo
T
T
Hwa
M
M
Lässig
D000465:Algorithms; D001185:Artificial Intelligence; D004247:DNA / Q000235:genetics; D008390:Markov Chains; D015233:Models, Statistical; D011506:Proteins / Q000235:genetics; D016415:Sequence Alignment / Q000706:statistics & numerical data*
D011506:Proteins; D004247:DNA