  The gapped local alignment score of two random sequences follows a Gumbel
distribution. If computers could estimate the parameters of the Gumbel
distribution within one second, the use of arbitrary alignment scoring schemes
could increase the sensitivity of searching biological sequence databases over
the web. Accordingly, this article gives a novel equation for the scale
parameter of the relevant Gumbel distribution. We speculate that the equation
is exact, although present numerical evidence is limited. The equation involves
ascending ladder variates in the global alignment of random sequences. In
global alignment simulations, the ladder variates yield stopping times
specifying random sequence lengths. Because of the random lengths, and because
our trial distribution for importance sampling occurs on a different sample
space from our target distribution, our study led to a mapping theorem, which
led naturally in turn to an efficient dynamic programming algorithm for the
importance sampling weights. Numerical studies using several popular alignment
scoring schemes then examined the efficiency and accuracy of the resulting
simulations.
