The Smith-Waterman algorithm for local sequence alignment is one of the mos
t important techniques in computational molecular biology. This ingenious d
ynamic programming approach was designed to reveal the highly conserved fra
gments by discarding poorly conserved initial and terminal segments. Howeve
r, the existing notion of local similarity has a serious flaw: it does not
discard poorly conserved intermediate segments. The Smith-Waterman algorith
m finds the local alignment with maximal score but it is unable to find loc
al alignment with maximum degree of similarity (e,g, maximal percent of mat
ches). Moreover, there is still no efficient algorithm that answers the fol
lowing natural question: do two sequences share a (sufficiently long) fragm
ent with more than 70% of similarity? As a result, the local alignment some
times produces a mosaic of well-conserved fragments artificially connected
by poorly-conserved or even unrelated fragments. This may lead to problems
in comparison of long genomic sequences and comparative gene prediction as
recently pointed out by Zhang et al, (Bioinformatics, 15, 1012-1019, 1999).
In this paper we propose a new sequence comparison algorithm (normalized l
ocal alignment) that reports the regions with maximum degree of similarity.
The algorithm is based on fractional programming and its running time is O
(n(2) log n). In practice, normalized local alignment is only 3-5 times slo
wer than the standard Smith-Waterman algorithm.