Comparative biosequence metrics |
| |
Authors: | T. F. Smith M. S. Waterman W. M. Fitch |
| |
Affiliation: | (1) Northern Michigan University, 49855 Marquette, Michigan, USA;(2) Los Alamos Scientific Laboratory, 87545 Los Alamos, New Mexico, USA;(3) Department of Physiological Chemistry, University of Wisconsin, 1215 Linden Drive, 589 Medical Sciences Building, 53706 Madison, Wisconsin, USA |
| |
Abstract: | Summary The sequence alignment algorithms of Needleman and Wunsch (1970) and Sellers (1974) are compared. Although the former maximizes similarity and the latter minimizes differences, the two procedures are proven to be equivalent. The equivalence relations necessary for each procedure to give the same result are: 1, the weight assigned to gaps in the Sellers algorithm exceed that in the Needleman-Wunsch algorithm by exactly half the length of the gap times the maximum match value; and 2, for any pair of aligned elements, the degree of similarity assigned by the Needleman-Wunsch algorithm plus the degree of dissimilarity assigned by the Sellers algorithm equal a constant. The utility of the algorithms is independent of the nature of the elements in the sequence and could include anything from geological sequences to the amino acid sequences of proteins. Examples are provided using known nucleotide sequences, one of which shows two sequences to be analogous rather than homologous. |
| |
Keywords: | Analogy Convergence Distance Divergence Homology Needleman-Wunsch-algorithm Sellers-algorithm Sequence-alignment |
本文献已被 SpringerLink 等数据库收录! |
|