For a guess \(\fm\) of \(\g\): Compute all states with \begin{equation} \gap(s, u) \leq \fm,\label{doubling} \end{equation} where \(\gap(s, \st ij)\) is the cost of indels (gapcost) needed to go from \(s\) to \(\st ij\). Instead of visiting states by column \(i\) or distance \(g\), we can order by \begin{equation} f(u) := g(u)+h(u) \leq \g,\label{astar} \end{equation} where \(h\) is any heuristic function satisfying \(h(u) \leq d(u, t)\). Goal: Diagonal Transition + pruning + local doubling Link to heading