INTRODUCTION

Dynamic programming is an effective tool for finding a solution for certain types of relatively small, non-linear problems. In biology, dynamic programming is used for pairwise alignment of amino acid sequences Needleman and Wunsch (1970). In electrical engineering, it is used for error correction in wireless communication and speech recognition Hosom et al. (1999) among many other things. We can also find examples of its use in geophysics. Kruse (1988) used dynamic programming for signal correlation and trace interpolation. He calculates an error function based on the difference in instantaneous frequency between all points along two signals. Dynamic programming is then used to find the error path with the least energy. Zhang (1991) used it for a starting solution when doing event picking.

In this paper we will continue the work started in Liner and Clapp (2002). We use dynamic programming for trace alignment. The Needleman-Wunsch algorithm Needleman and Wunsch (1970) proves effective when we expect significant stretch between compared traces, while alternate dynamic programming approaches can be more effective when we expect smoother variations and desire continuity between alignments.

In this paper we begin by discussing the basic tenets of dynamic programming and the specific features of both algorithms. We show how to extend the algorithms to seismic trace alignment and apply them on several different types of alignment problems.