Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology (1995)
Chapter: Visualizing Alignments: Edit Graphs
Page 59
The unit-cost scoring scheme of Figure 3.1 is not the only possible scheme. Later in this chapter, we will see a much more complex scoring scheme used in the comparison of proteins (20-letter alphabet). In that scheme and other scoring schemes, the scores in the table are real numbers assigned on the basis of various interpretations of empirical evidence. Let us introduce here a formal framework to assist our thinking.
Figure 3.1
Unit-cost scoring scheme.
Consider comparing sequence A = a1a2···aM and sequence B = b1b2··· bN, whose symbols range over some alphabet y, for example, y = {A,C,G,T} for DNA sequences. Let d (a,b) be the score for aligning a with b, let d(a,-) be the score of leaving symbol a unaligned in sequence A, and let d(-,b) be the score of leaving b unaligned in B. Here a and b range over the symbols in y and the gap symbol "-". The score of an alignment is simply the sum of the scores d assigns to each pair of aligned symbols, for example, the score of 
is
d(A,A) + d (T,-) + d (T,T) + d (A,A) + d (-,T) + d (C,C) + d (G,G), which for the scoring scheme of Figure 3.1 equals 5. An optimal alignment under a given scoring scheme is an alignment that yields the highest sum.
Visualizing Alignments: Edit Graphs
Many investigators have found it illuminating to convert the problem of finding similarities into one of finding certain paths in an edit graph.
