ON GLOBAL SEQUENCE ALIGNMENT

We present a dynamic programming algorithm for computing a best global alignment of two sequences. The proposed algorithm is robust in ident ifying any of several global relationships between two sequences. The algorithm delivers a best alignment of two sequences in linear space a nd quadratic time. We also describe a multiple alignment algorithm bas ed on the pairwise algorithm. Both algorithms have been implemented as portable C programs. Experimental results indicate that for a commonl y used set of gap penalties, the new programs produce more satisfactor y alignments on sequences of various lengths than some existing pairwi se and multiple programs based on the dynamic programming algorithm of Needleman and Wunsch.