In article <920629220811.21a51350 at sds.sdsc.edu> gribskov at SDSC.EDU (Michael Gribskov) writes:
>> It seems unlikely that such a matrix has been used with the
> Needleman-Wunsch algorithm. As you may recall, the NW algorithm (Needleman
> and Wunsch, J. Mol. Biol. 48, 443-453, 1970) does not use an affine gap
> cost, although they do suggest that the "penalty factor could be a function
> of the size and/or direction of the gap". NW requires a scoring table with
> all positive values since only the last row and column of the alignment
> matrix are examined for the maximum score. A scoring table with negative
> values is not guaranteed to give an optimum alignment with the NW
> algorithm. ...
I believe this statement to be incorrect. While Needleman and
Wunsch used a length independent gap penalty, there was no requirement
that the substitution values be positive. A global algorithm, such as
N&W, does require that score be that calculated for the last row and
column, but it places no limits on the scoring matrix. A globally
optimal score will be found with N&W even if all the substitution
values are negative.
It is true, of course, that if the substitution matrix has
both positive and negative scores, it is likely that there will be a
locally optimal score (and alignment) that is different from the
globally optimal score. And, if all the scoring matrix values (and
gap penalties) are 0 or greater, the optimal global and local scores
(and alignments) will be the same.
Bill Pearson
