Although segment based comparison methods (see section 3.1) rely on local comparisons, if insertions and deletions have occurred, the match may be disrupted for a region of the order of the length of the segment. In order to circumvent these difficulties algorithms which are modifications of the basic global alignment methods have been developed to locate common subsequences including a consideration of gaps (e.g.[31][30][29]). For protein sequences, the most commonly used local alignment algorithm that allows gaps is that described by Smith and Waterman [30]. This is essentially the same as the global alignment algorithm described in section 3.2.1, except that a zero is added to the recurrence equation.
Thus all must
have a value
. The score for the best local alignment is simply
the largest value of
and the coresponding alignment is obtained by
tracing back from this cell.