Approximate p-values for local sequence alignments

Siegmund and Yakir (2000) have given an approximate p-value when two independent, identically distributed sequences from a nite alphabet are optimally aligned based on a scoring system that rewards similarities according to a general scoring matrix and penalizes gaps (insertions and deletions). The approximation involves an innite sequence of difcult-to-compute parameters. In this paper, it is shown by numerical studies that these reduce to essentially two numerically distinct parameters, which can be computed as one-dimensional numerical integrals. For an arbitrary scoring matrix and afne gap penalty, this modied approximation is easily evaluated. Comparison with published numerical results show that it is reasonably accurate. Key words: local alignment, afne gap penalty, p-value, Markov renewal theory. 1