Analyzing the merit of an alignment is equivalent to analyzing the merit
of the corresponding path in the edit graph. Given any two strings, there
are a large number of different alignment matrices and corresponding paths
in the edit graph. Some of these have a surplus of mismatches and indels
and a small number of matches, while others have many matches and few
indels and mismatches. To determine the relative merits of one alignment
over another, we rely on the notion of a scoring function, which takes as
input an alignment matrix (or, equivalently, a path in the edit graph) and
produces a score that determines the “goodness” of the alignment. There are
a variety of scoring functions that we could use, but we want one that gives
higher scores to alignments withmorematches. The simplest functions score
a column as a positive number if both letters are the same, and as a negative
number if the two letters are different. The score for the whole alignment is
the sum of the individual column scores. This scoring scheme amounts to