Critical Phenomena for Sequence Matching with Scoring

Consider two independent sequences X₁,…, Xₙ and Y₁,…, Yₙ. Suppose that X₁,…, Xₙ are i.i.d. μ X and Y₁,…, Yₙ are i.i.d. μY, where μX and μY are distributions on finite alphabets ∑X and ∑Y, respectively. A score F: ∑X × ∑Y → R is assigned to each pair (Xᵢ, Yⱼ) and the maximal nonaligned segment score is Mₙ = max0≤ i, j ≤ n - Δ, Δ ≥ 0\∑^Δₗ₌₁F(Xᵢ₊ₗ, Yⱼ₊ₗ)\. Our result is that Mₙ/log n → γ⁽μX, μY) a.s. with γ^ determined by a tractable variational formula. Moreover, the pair empirical measure of (Xᵢ₊ₗ, Yⱼ₊ₗ) during the segment where Mₙ is achieved converges to a probability measure ν^, which is accessible by the same formula. These results generalize to Xᵢ, Yⱼ taking values in any Polish space, to intrasequence scores under shifts, to long quality segments and to more than two sequences.