Details of the algorithm

We now introduce a more flexible form to the Needleman-Wunsch algorithm Karp (2000). Let the two input strings, (x,y), given by

$$\begin{eqnarray} x &=& (x_1,x_2,~...~,x_i,~...~,x_m) \\ y &=& (y_1,y_2,~...~,y_j,~...~,y_n)\end{eqnarray}$$ (1) (2)

where (m,n) need not be equal. The subscript i denotes the row direction, and j denotes columns. We write the scoring function V(i,j) as the equation set

$$\begin{eqnarray} V(i,j) &=& max\left[ {G(i,j), F(i,j),E(i,j)} \right] \\ G(i,j) ... ...V(i,n+1) &=& -(p +(m-i+1)~q) \\ V(m+1,j) &=& -(p+(n-j+1)~ q) ~~~~,\end{eqnarray}$$ (3) (4) (5) (6) (7) (8)

where the indices range $i \leq m$ and $j \leq n$.In this form, the function $\sigma (x_i,y_j)$ is the similarity matrix and it is calculated on the fly rather than precomputed. Further it can be customized to reflect different weights associated with matches and mismatches. In biological applications an element on each string either matches or does not, and this fact is represented in the choice of a similarity measure, for example     

$$\sigma (x_i,y_j) = \left\{ \begin{array} {llll} \sigma(a,a)... ...&\\ \sigma(-,a) = 0 &\\ \sigma(a,-) = 0 &\end{array} \right .$$ (9)

in which a value of 1 is awarded for a match, and all other cases are are equally awarded .

In the seismic case we do not expect or need an exact amplitude match, rather it is important to reward small amplitude differences and penalize large ones. We capture this idea in a similarity function as

$$\sigma (x_i,y_j) = c - abs[ t_1(x_i) - t_2(y_j)] ,$$ (10)

 where c is a constant chosen to keep $\sigma (x_i,y_j)\gt$and abs[] is the absolute value.

Computational complexity and cost of this algorithm applied to two strings of length n and m is O(n*m).