Lower bounds for optimal alignments of binary sequences

In parametric sequence alignment, optimal alignments of two sequences are computed as a function of matches, mismatches and spaces, producing many different optimal alignments. In the two-parameter case, Gusfield et al shows that the number of distinct optimal alignment summaries for a pair of sequences is O(n2/3)O(n2/3). Here we construct binary sequences of length nn with 3/(27/3π2/3)n2/3+O(n1/3logn)3/(27/3π2/3)n2/3+O(n1/3logn) distinct optimal alignment summaries. This shows that the upper bound given by Gusfield et al. is tight over all alphabets, thereby disproving the “n conjecture”. Thus the maximum number of distinct optimal alignment summaries over all pairs of length nn sequences is Θ(n2/3)Θ(n2/3).