ABSTRACT
In 1970, dynamic programming was first applied to the comparison of biological sequences by Needleman and Wunsch. Their method is now called a similarity method. Since their work, many extensions and modifications have been introduced. This includes distance methods, general gap functions, multiple alignment procedures, and near-optimal methods. The chapter argues that DNA sequences, but the general theory allows analysis of protein and other sequences. It provides a tentative analysis of a multiple inference procedure presented in S. F. Altschul and B. W. Erickson. They propose as a measure of sequence similarity the minimal attained significance among all runs of matches, minimizing over all possible run lengths. When more sequences began to appear in the later 1970's, it became apparent that alignment of entire sequences was frequently not the major problem of interest.
