SEQUENCE ALIGNMENT (and many other similar problems) can be resolved with dynamic programming in O(mn) time.

E.g.

AGARSARF_GSSAGRGGGGEPEGRPGPFNG
|:|||:.. |:::|.|||||||||:|:.||
ASARSGSSAGGGGGGGGGGEPEGRSGSSNG

For this we construct a MATRIX of OPTIMAL SCORING



The computation of each optimum is usually described as:

next previous