Bounds for parametric sequence comparison

AbstractWe 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(n1/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(n2/3) upper bound by Gusfield et al., answering a question posed by Pevzner and Waterman. Our lower bound requires an unbounded alphabet. For strings over a binary alphabet, we prove a Ω(n1/2) lower bound. For the parametric global alignment of k⩾2 sequences under sum-of-pairs scoring we prove a 3((k2)n/2π)2/3+O(k2/3n1/3logn) upper bound on the number of distinct optimality regions and a Ω(n2/3) lower bound, partially answering a problem of Pevzner. Based on experimental evidence, we conjecture that for two random sequences, the number of optimality regions is approximately n with high probability