Bounds for parametric sequence comparison

We consider the problem of computing a global alignment between two or more sequences subject to varying mismatch and indel penalties. We prove a tight 3(n/2π)^2/3+O(n^1/3logn) bound on the worst-case number of distinct optimum alignments for two sequences of length n as the parameters are varied. This refines a O(n ^2/3) upper bound by D. Gusfield et al. (1994). Our lower bound requires an unbounded alphabet. For strings over a binary alphabet, we prove a Ω(n^1/2) lower bound. For the parametric global alignment of k⩾2 sequences under sum-of-pairs scoring, we prove a 3((k/2)n/2π)^2/3+O(k^2/3n^1/3logn) upper bound on the number of distinct optimality regions and a Ω(n ^2/3) lower bound. Based on experimental evidence, we conjecture that for two random sequences, the number of optimality regions is approximately √n with high probability