A fast homology program for aligning biological sequences.
The algorithm of Gotoh computes in two passes of MN steps the alignment of a pair of sequences of lengths M and N, subject to a constraint on the form of the gap weighting function. This compares with the previous algorithm of Waterman et al. which runs in M2N steps. Gotoh also gave a method using two passes of (L+2)MN steps in the case where gap weights remain constant for gaps of length greater than L. Here we describe a procedure for computing the alignment (evolutionary distance and optimal path) in a single pass of MN steps for both cases.
D000595:Amino Acid Sequence; D001483:Base Sequence; D005075:Biological Evolution; D003201:Computers; D004247:DNA / Q000235:genetics*; D008905:Minicomputers; D008957:Models, Genetic; D011506:Proteins / Q000235:genetics; D012984:Software
D011506:Proteins; D004247:DNA