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:
![]()
![]() |
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).