Rapid Significance Estimation in Local Sequence Alignment with Gaps

Abstract

In order to assess the significance of sequence alignments, it is crucial to know the distribution of alignment scores of pairs of random sequences. For gapped local alignment, it is empirically known that the shape of this distribution is of the Gumbel form. However, the determination of the parameters of this distribution is a computationally very expensive task. We present a new algorithmic approach which allows estimation of the more important of the Gumbel parameters at least five times faster than the traditional methods. Actual runtimes of our algorithm between less than a second and a few minutes on a workstation bring significance estimation into the realm of interactive applications.