SAMBA ALGORITHM

The algorithm implemented on SAMBA belongs to the dynamic programming class. The recurrence equation comes from the Smith and Waterman algorithm. However, it has been adapted - parametrized - to cover a larger scope. A similarity matrix is calculated recursively using the following equation:

                    | delta 
      H(i,j) = Max  | E(i,j)
                    | F(i,j)
                    | H(i-1,j-1) + SUB(S1i,S2j) 
       with:

      E(i,j) = Max (H(i,j-1)-alpha,E(i,j-1)-beta)
      F(i,j) = Max (H(i-1,j)-alpha,F(i-1,j)-beta)

      and the initializations given by:

      H(i,0) = E(i,0) = hi(i)   H(0,j) = F(0,j) = vi(j)

alpha, beta, delta, hi and vi are parameters for tuning the algorithm to local or global search, with or without gap penalty.

EXAMPLES :

global alignment with simple gap cost requires:

  delta = -infinity     alpha = g     beta = g      hi(i) = vi(i) = -g x i

local alignment with cut and extension gap cost requires:

  delta = 0    alpha = gcut     beta = gext     hi(i) = vi(i) = 0