DynamicProgramming의 한계는 memory usage. score matrix F(i,j) size nm.

Linear space method : n+m rather than nm

If looking for a LocalAlignment we need to find the maximum score in the whole matrix, but it is easy to keep track of the maximum value as the matrix is being built. --> score는 주지만, alignment는 찾을 수 없다. 즉 O(nm) space를 피하기 위해 rows를 버린다면 traceback pointers도 잃기 때문이다. use DivideAndConquer.

u = n/2, i=u일때의 alignment상의 match j를 v로 놓고, from (0,0) to (u,v) and from (u,v) to (n,m) 두 부분으로 쪼개어짐. 따라서 space가 반으로 줄어든다.

v는 어떻게 구하느냐?

For i > u. define c(i,j). 
(u, c(i,j)) is on the optimal path from (1,1) to (i,j). 
calculate F(i,j) --> F(i', j'). 
set c(i,j)=j' if i=u, else c(i,j)=c(i',j')

finding v --> MyersMillerAlgorithm: dose not propagate the traceback pointer c(i,j), but instead finds the midpoint (u,v) by combining the results of forward and backward DynamicProgramming at row u.

in 1995, Waterman gives a 3rd linear space approach.