A fast homology program for aligning biological sequences
- 1 January 1984
- journal article
- Published by Oxford University Press (OUP) in Nucleic Acids Research
- Vol. 12 (1Part2) , 447-455
- https://doi.org/10.1093/nar/12.1part2.447
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- An improved algorithm for matching biological sequencesPublished by Elsevier ,2004
- Pattern recognition in nucleic acid sequences. I. A general method for finding local homologies and symmetriesNucleic Acids Research, 1982
- Comparative biosequence metricsJournal of Molecular Evolution, 1981
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970