LinearSpaceAlignment pseudocode

forget-the-past.tex

\begin{algorithm}
\caption{Calculates the optimal alignment using ForgetThePast-NW}
\begin{algorithmic}
\Procedure{LinearSpaceAlignment}{$S$, $T$}
\State m = \textbf{length}(S)
\State n = \textbf{length}(T)
\If {$m <= 1$ \textbf{or} $n <= 1$}
\State \textbf{return} NW(S, T) \Comment Use the regular NW algorithm
\Else \Comment Divide and conquer with recursion
\State Middle = \textbf{round}(m/2)
\State SLeft = ForgetThePast-NW(S[0: Middle]) \Comment Returns last row of NW table
\State SRight = ForgetThePast-NW(S[Middle : m]) \Comment Returns reverse of last row of NW table
\State Split = j \textbf{maximizing} SLeft[j] + SRight[j + 1] \Comment Where 1 $<$ j $<$ m + 1
\State \textbf{return concatenation of} LSA(SLeft, T[0 : Split]) + LSA(SRight, T[Split : n]) 
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}