Back to dynamic programming

There are several ways we can try to improve the result seen in the left panel of Figure 5. We can think of smoothing the paths through the score matrix. We can also make some reasonable a priori assumptions. We can add to our similarity matrix. We might put large weights in the matrix by saying that time 0 should be the same in the PP and PS section or by visually matching a single reflector. These approaches improve our result, but still lead to something less than ideal.

A better solution is to return to a more generic form of dynamic programming. We can improve our 1-D estimates by remembering that what we are really doing is estimating a $\frac{v_p}{v_s}$ratio. This ratio has to be a continuous function of time, as a result it is not reasonable to have large gaps in our trace alignment. First, if we consider the traces to be samples in a PP gather, we can assume that the our alignment function will be single valued. As a result, we can make our series of decisions one PP time element at a time. Changing our decision definition takes away the nice feature of the NW algorithm that we only have to consider three states at each decision. On the other hand, we can limit ourselves to considering the subset of states that correspond to a reasonable $\frac{v_p}{v_s}$ path. We know that each PP sample must correspond to the previous PP sample +x, where x is a very small number. As a result, we again need to only consider two to four states at each decision. The right panel of Figure 5 shows the result of applying this dynamic programming concept, along with the constraints discussed above, to the Alba alignment problem. Note how the solution is better than the result shown in the left panel of Figure 5, but still could be improved.