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: