  We consider the following model for sampling pairs of strings: $s_1$ is a
uniformly random bitstring of length $n$, and $s_2$ is the bitstring arrived at
by applying substitutions, insertions, and deletions to each bit of $s_1$ with
some probability. We show that the edit distance between $s_1$ and $s_2$ can be
computed in $O(n \ln n)$ time with high probability, as long as each bit of
$s_1$ has a mutation applied to it with probability at most a small constant.
The algorithm is simple and only uses the textbook dynamic programming
algorithm as a primitive, first computing an approximate alignment between the
two strings, and then running the dynamic programming algorithm restricted to
entries close to the approximate alignment. The analysis of our algorithm
provides theoretical justification for alignment heuristics used in practice
such as BLAST, FASTA, and MAFFT, which also start by computing approximate
alignments quickly and then find the best alignment near the approximate
alignment. Our main technical contribution is a partitioning of alignments such
that the number of the subsets in the partition is not too large and every
alignment in one subset is worse than an alignment considered by our algorithm
with high probability. Similar techniques may be of interest in the
average-case analysis of other problems commonly solved via dynamic
programming.
