Asymptotic Distribution for Sequence Alignment Scores

Alignment score distributions have become very important for computing p-values of alignments built on database searches based on adjustable measures of similarity. Such scores provide a level of flexibility allowing for different measures of similarity, as well as for seeking candidates for RNA binding sites. However, computation of the probability distribution over its full range has proven complex, with a great deal of interest focusing on the scaling dependence of probabilities on alignment sequence lengths. This paper presents a distribution function derived from first principles that describes the sequence-length dependence and extreme-value behavior of an arbitrary matrix of alignment scores given their alignment species frequencies. The derivation is based on the asymptotic Sterling’s formula applied in the continuum limit. The results are compared to simulation results for alignment sequence lengths ranging from 10 to 10,000, with observed binned frequencies down to the order of 10⁻⁷ , and seen to produce good approximations for probabilities of practical sequence alignment lengths. This distribution function provides a practical and fairly easy to compute baseline against which the behavior of real and simulated data may be measured.