  The edit distance between strings classically assigns unit cost to every
character insertion, deletion, and substitution, whereas the Hamming distance
only allows substitutions. In many real-life scenarios, insertions and
deletions (abbreviated indels) appear frequently but significantly less so than
substitutions. To model this, we consider substitutions being cheaper than
indels, with cost $1/a$ for a parameter $a\ge 1$. This basic variant, denoted
$ED_a$, bridges classical edit distance ($a=1$) with Hamming distance
($a\to\infty$), leading to interesting algorithmic challenges: Does the time
complexity of computing $ED_a$ interpolate between that of Hamming distance
(linear time) and edit distance (quadratic time)? What about approximating
$ED_a$?
  We first present a simple deterministic exact algorithm for $ED_a$ and
further prove that it is near-optimal assuming the Orthogonal Vectors
Conjecture. Our main result is a randomized algorithm computing a
$(1+\epsilon)$-approximation of $ED_a(X,Y)$, given strings $X,Y$ of total
length $n$ and a bound $k\ge ED_a(X,Y)$. For simplicity, let us focus on $k\ge
1$ and a constant $\epsilon > 0$; then, our algorithm takes $\tilde{O}(n/a +
ak^3)$ time. Unless $a=\tilde{O}(1)$ and for small enough $k$, this running
time is sublinear in $n$. We also consider a very natural version that asks to
find a $(k_I, k_S)$-alignment -- an alignment with at most $k_I$ indels and
$k_S$ substitutions. In this setting, we give an exact algorithm and, more
importantly, an $\tilde{O}(nk_I/k_S + k_S\cdot k_I^3)$-time
$(1,1+\epsilon)$-bicriteria approximation algorithm. The latter solution is
based on the techniques we develop for $ED_a$ for $a=\Theta(k_S / k_I)$. These
bounds are in stark contrast to unit-cost edit distance, where state-of-the-art
algorithms are far from achieving $(1+\epsilon)$-approximation in sublinear
time, even for a favorable choice of $k$.
