Any matrix with a formula involving a finite number of

Optst      (s+t < i+j)
and possibly
max( Optst+ks, s=1..i-1 )

can be resolved in O(mn) time.

- Usually we need very efficient code.



- Avoid O(mn) storage, use only O( min(m,n) ) storage. efficient code.



Find the optimal alignment itself (not just the optimal score). This can be done efficiently with a divide and conquer technique.



Code example.

next previous