An Extreme Value Theory for Sequence Matching

Consider finite sequences X₁, X₂,⋯, Xₘ and Y₁, Y₂,⋯, Yₙ where the letters Xᵢ and Yᵢ are chosen i.i.d. on a countable alphabet with p=P(X₁=Y₁)∈(0,1) We study the distribution of the longest contiguous run of matches between the X's and Y's allowing at most k mismatches. The distribution is closely approximated by that of the maximum of (1 - p)mn i.i.d. negative binomial random variables. The latter distribution is in turn shown to behave like the integer part of an extreme value distribution. The expectation is approximately log(qmn)+kloglog(qmn)+klog(q/p)-log(k!)+γlog(e)-1/2, where q = 1 - p, log denotes logarithm base 1/p, and y is the Euler constant. The variance is approximated by (πlog(e))2/6+1/2. The paper concludes with an example in which we compare segments taken from the DNA sequence of the bacteriophage lambda.