Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatic Analysis
Substitution Matrices
Weights of Edit Operations

Not all biological sequence substitutions are equivalent. For instance, conservative Amino Acid Substitutions preserve protein functionality, whereas radical ones can lead to a loss of function. Furthermore, the high noise Immunity of METABOLISM/28.html">The Genetic Code means that conservative Mutations are much more likely to occur than radical ones (see [7], sec. 4.2.1). As another example, a deletion of adjacent nucleic acid bases in nucleic acid molecules or adjacent Amino Acids in Proteins is a much more probable event than the deletion of the same number of randomly positioned locations within a biological sequence. Therefore, when calculating the distance between sequences, each type of editing is assigned a different "weight" or "score".

It is important to keep in mind a terminological nuance specific to this type of scoring. In biology, it is standard practice to assign a score to sequence alignments based on their degree of similarity; thus, similar sequences yield high scores, whereas dissimilar ones yield low scores.

Conversely, distance determination (using Hamming or Levenshtein distance) measures the dissimilarity between two sequences—similar sequences result in small distance values, whereas dissimilar ones yield large values.

The algorithm for constructing an optimal alignment must either minimize the distance or maximize the alignment score.

To obtain an optimal score, it is necessary to add points for each pair of matching characters in the alignment (diagonal transitions in Figure 18) and subtract points (penalize) for insertions and deletions, or indels (vertical and horizontal transitions in Figure 18).

Since it is impossible to distinguish between an insertion and a deletion when comparing two sequences, the compound term "indel" (derived from "insertion" + "deletion") is frequently used in English-language literature. While Russian literature sometimes employs the literal equivalent "инсдел" (or even "всуд" from "вставка" + "удаление"), we will consistently use the term "deletion" here to avoid unnecessary complexity.

Three types of deletion penalties are used in various Applications:

1) fixed penalty: y = -d;

2) linear penalty, where the cost of deleting $g$ residues is determined by a linear function: y(g) = -gd;

3) affine penalty: y(g) = -d - (g-1)e, which consists of a penalty $-d$ for introducing a deletion (gap-open) and a penalty $-e$ for extending the deletion (gap-extension).

Nucleic Acids. For scoring substitutions in nucleic acids, the simplest approach adds a (+1) bonus for a match and imposes a (-1) penalty for a mismatch. More sophisticated scoring schemes take into account, for example, the fact that transitions (transition mutation)—substitutions of purine↔purine and pyrimidine↔pyrimidine ($a↔g$ and $t↔c$)—occur significantly more often than transversions (transversion mutation)—substitutions of purine↔pyrimidine ($a, g$)↔($t, c$).

As an example, Table 7 presents one possible nucleotide substitution matrix.

Class="center">Table 7 - Nucleotide substitution matrix

When aligning DNA sequences, the ClustalW program recommends using values of "+1" for a match, "0" for a mismatch, along with a gap-opening penalty of $d = 10$ and a gap-extension penalty of $e = 0.1$.

Amino acid sequences. Several substitution schemes have been proposed for amino acid sequences.

It is well known that certain types of amino acid substitutions are commonly observed in homologous proteins across different species. Because a protein carrying these substitutions remains functionally active, the substituting Amino acids are evidently compatible with its Structure and function. Such replacements frequently occur between chemically similar amino acids, though Other types of changes also appear, albeit relatively rarely.

Knowing the frequencies of all types of substitutions occurring in various proteins (derived from a large dataset) can assist in predicting alignments for any set of protein sequences.

If the sequences of related proteins are highly similar, they are easy to align, allowing researchers to readily trace all amino acid substitutions that occurred during recent evolutionary stages. Once the Phylogenetic relationships among a group of proteins have been preliminarily established, the most likely evolutionary amino acid substitutions can be predicted.

This analytical method was proposed and introduced into scientific practice by Margaret Belle (Oakley) Dayhoff (1925–1983). She compiled statistics on the frequencies of amino acid substitutions in known proteins, and her results were used for alignment scoring for many years. Subsequently, they were superseded by newer matrices derived from the Processing of newly sequenced genomes.