Symbol Comparison Tables
Nucleic acid sequence alignment will succeed if the scoring
proceeds according to a simple match/mismatch schema. Sophisticated
approaches will include ambiguity tables and score a match of
G to S as half the match score
- S is the ambiguity letter for G or C. However, most DNA sequences
follow a 4-letter alphabet and, therefore, will be satisfactorily
handled with straightforward matching score calculation.
Protein comparisons are more sophisticated.
One option to compare amino acids by property is to set up a
classification for
etc.
As it is difficult to quantify these properties, measurable values
could be used like
etc.
The comparison tables which are generated this way might be based
on correct values, however, miss the target as the value of a
comparison matrix will be determined by the potential to follow
the basic paradigm which we imply in performing the alignment:
DNA sequence
determines |
V
protein sequence
determines |
V
secondary structure
determines |
V
tertiary structure (protein)
determines |
V
protein function
Two approaches have been used successfully in standard
implementations of biocomputing software:
- Evolutionary Approach:
The analysis of globular protein structure evaluated with X-ray
crystallography allowed Dayhoff et al. to set
up a comparison matrix which honours or penalises amino acid
substitutions. As proteins were found to allow exchange at certain
positions, whereas other substitutions were never found, it was
possible to postulate a comparison matrix based on the number
of accepted point mutations (PAM 250), which
is widely used. Note that the values therein are averages which
are calculated on a limited number of proteins - the sequence
databases are much larger by today as compared to the crystallographic
databases known at the time of the PAM250 matrix creation.
- Alignment Approach
Based on the PROSITE database of Amos Bairoch,
the alignments of many protein motifs were used by Hennikoff
et al. to compute a matrix which is commonly known as
BLOSUM62 in the most widely used variant. The
benefit of this matrix is that a very large number of alignments
was the basis for its creation, which allowed more "sensitive"
comparisons than the PAM250 matrix.
Many more matrices have been proposed but are not currently
widely used.
NOTE: It is essential to understand the impact of the
symbol comparison matrix for the result of the calculation; in
particular as the statistics or numerical values of results will
reflect the underlying matrix. "Good" or "meaningful" alignments
as numerically computed by a program are only as good as the
algorithm, but the relevance for biology is also affected by
the relevance or applicability of the matrix used for comparison.
Alignment Path Matrices
NOTE:
The following description tries to explain the method but does
not show the real implementation for reasons of simplicity and
brevity. Please refer to the original papers for further reference.
Advanced users should skip this section and proceed reading the
"programs"section
.
The basic principle of an alignment path matrix is the stepwise
creation of values. Figure E shows
the initial step: As in the 'dotplot' program, sequences were
painted in a crossword-like fashion. Instead of a dot, the match
or mismatch value is printed.
Next, additional values are calculated by adding the value of
the current field (match or mismatch value) in addition to the
value of an alignment path seen before arriving at this step.
Figure F shows the alignment path matrix in
an intermediate stage. Each new value is printed as the minimum
of one of several possibilities. To get to the value (X)
in the Figure, one could use one of several possible
pathways:
one gap: 1 (previous) -5 (gap) -1 (mismatch)
/ = -5
/ direct: -3 (previous) -1 (mismatch) = -4
+------+------+------+// one gap: 0 (previous) -5 (gap) -1 (mismatch)
c | -1 | -2 | 0 /// one longer gap: = -6
+------+------______////----+ 6 (previous) -5 (gap) -1 (gap length)
t | -1 | 1 /| -3 /// -1 | -1 (mismatch) = -1
+------+------+-----||------+
g | -1 | -2 | 0/ | 8 |
+------+------+-----/+------+ min of (-5, -4, -6, -1) = -1
g | -1 | -2 | 6/ | -1 | value printed, therefore: -1
+------+------+------+------+
...| | | |
a t g g
To compute all beneficial fields quickly, some implementations
do not compute "chanceless" pathways and reduce, therefore, memory
and time requirements. This, typically, applies to the edges
of sequence alignment path matrices (in our example, the upper
left and lower right corner). The GCG program implementation
claims a "value not guaranteed to be optimal" but usually the
edges do not yield a much better value.
Figure E: Alignment path matrix, step 1 Scores
are computed as outlined in the text.
g -1
a 2
a 2
g -1
t -1
a 2
t -1
c -1
a 2
a 2
a 2
t -1
g -1
a 2
a 2
c -1
t -1
g -1
g -1
t -1
a 2
g -1
t -1 2 -1 -1 2 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 2 2 2
a t g g t a a t g g c a c a a t t g a c t t t
Figure F: Alignment path matrix in an
advanced stage. Scores are calculated as described in the text
using the following values: direct: score + previous. score value
= 2 gap: score + previous -5 mismatch = -1 gap length = -1 Note
the (X) which is explained in detail in the text.
g -1 1 3
a 2 1 -3
a 2 -2 -3
g -1 -2 6
t -1 4 -3
a 2 -2 0
t -1 1 0
c -1 1 0
a 2 1 0
a 2 1 -3
a 2 -2 0
t -1 1 0
g -1 1 3
a 2 1 -3
a 2 -2 -3
c -1 -2 0 (X)
t -1 1 -3 -1
g -1 -2 0 8
g -1 -2 6 -1
t -1 4 -3 -4
a 2 -2 -3 3 0 0 3 -3 -3 3 0 0 -3 0 0 -3 -3 0 6 -3 -3 -3 0
g -1 -2 4 1 -2 1 -2 -2 4 1 -2 -2 -2 -2 -2 -2 1 4 -2 -2 -2 1 1
t -1 2 -1 -1 2 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 2 2 2
a t g g t a a t g g c a c a a t t g a c t t t
The final result of the alignments is painted in Figure
G. 
JAMF source code
BioCompanion V2.x (1995)