Sequence Alignment as Graph Search

The Simplest Explanation

Given two strings (DNA letters A/C/G/T), align them by sliding in gaps to minimize total cost:

• Mismatch cost: two different characters aligned against each other
• Indel cost: a gap inserted in either string

This is exactly shortest-path search on an (n+1)×(m+1) grid where each cell is a partial alignment.

The Grid Model

Start node = top-left corner; goal = bottom-right. Every monotone path through the grid corresponds to exactly one alignment; its cost = sum of edge costs along the way.

Why Costs Matter

If indel penalty = 3 and mismatch penalty = 7, inserting two gaps (cost 6) beats one mismatch (cost 7). If the mismatch penalty drops to 5, accepting the mismatch wins. The optimal alignment depends entirely on this ratio — same strings, different answers.

The Scale Problem

Strings of length n and m give $(n{+}1)(m{+}1)$ cells:

Real biological sequences run hundreds of thousands of characters → astronomically many paths. Search algorithms (A*, Dijkstra) are needed, not naive enumeration.

Open vs Closed Growth — Why This Problem Matters

On the alignment grid:

• Open grows linearly — the frontier is at most about twice the grid width
• Closed grows quadratically ≈ area of explored region

For huge sequences, Closed dominates memory completely. This asymmetry is precisely why Frontier Search / SMGS (which delete Kernel Closed nodes) were invented — sequence alignment is their showcase application.

Properties