Optimal detection of sequence similarity by local alignment

The statistical properties of local alignment algorithms with gaps are analyzed theoretically for uucorrelated and corre-lated random sequences. In the viciuity of the log-linear phase transition, the statistics of alignment with gaps is shone to be characteristically different from that of gap-less alignment. The optimal scores obtained for uncorre-lated sequences obey certain robust scaling laws. Deviation from these scaling laws signals sequence homology, and can be used to guide the empirical selection of scoring parame-ters for the optimal detection of sequence similarities. This can be accomplished in a computationally efficient way by using a novel approach focusing on the score profiles. Fur-thermore, by assmting a few gross features characterizing the statistics of underlying sequence-sequence correlations, quantitative criteria are obtained for the choice of optimal scoring parameters: Optimal similarity detection is most likely to occur in a region close to the log side of the log-linear phase transitio