# Optimizations in the Salign Algorithm

To lower the computational complexity of the Salign search algorithm, it is necessary to reformulate the computation of the WA(I,J), as presented in Section 3.3. This reformulation requires that we assume P(m | n), the probability of observing a size m string as the translation of a size n string, to be the same for all values of m and n. Then, the value of becomes constant in the computation of the scoring function W(i,I,j,J), and the following relation holds:

We define Wp(I,J,i) to be the score of the best alignment over the pair of text prefixes s0 ... sI and t0 ... tJ, whose last correspondence covers segments si ... sI-1:

(See Figure 8.)

It is then possible to express the value of WA(I,J) in terms of Wp(I,J,i):

What makes this intermediate notation interesting is that the computation of each value of Wp(I,J,i) can be greatly simplified:

 Wp(I,J,i) = = = = =

Salign alternately computes rows of values of WA(I,J) and Wp(I,J,i), and stores them in a vector. Computing each value of WA(I,J) then requires O(N) time. Computing individual values of Wp(I,J,i) would normally require O(N2) time, but this can be cut down to O(N), if values of are pre-computed and stored, for each possible pair of values of i and I. This pre-computation step requires O(N2) time and space.

All things considered, the program must compute O(NM) values of WA(I,J) and Wp(I,J,i), so the overall computational complexity of the algorithm is O(N2M), while space complexity is O(N2).