Note
A sequence alignment is an intuitive overview of differences between two strings. It’s done by writing the two strings one below the other and highlighting where edit operation took place.
Alignment for minimum edit distance
Note
Let’s say that
is the edit distance between two strings and , and that is the prefix on length of an string. Given that we can give the recursive definition: If we set initially
and we can compute .
Practically speaking, we can make a matrix of
Once we’ve computed the edit distance, we need to get what’s the optimal series of operations to transform one string into another.
To do this we start from the cell
Efficient backtracking
For some cells there are multiple neighbouring cells which give the same minimum value, the choice between them is usually arbitrary.
The time complexity of the backtracking algorithm is
Weighted edit distance
By assigning a different weight to each operation (
for insertions and deletions, and for the symbols) we can define the weighted edit distance as:
Alignment based on sequence similarity
Note
We can evaluate similarity instead of distance between two strings. To do that we need to define and computer measures of similarity, such as:
- Percent identity: after the alignment we determine the percentage of the alignment which does not indicate an edit operation.
- Longest common subsequence (LCS): derived by deleting some, all or no character, the order of the remaining elements remains unchanged.
Let
and be two strings, and let and be prefixes of length and . Let be the length of the longest common subsequence. We can compute it using:
Practically we apply the same criteria as the edit distance table, but the backtracking algorithm adds one for diagonal cells and adds nothing for left and top cells.
Global sequence alignment based on distance and similarity
Note
By combining the previous two approaches into a single one we define a similarity measure for two strings
and such that:
- differences have a negative effect: there’s a negative weight for gap and mismatch, often called penalty.
- conserved letters have a positive effect: there’s a positive weight for match.
We can do that by using a combined alignment score
as follows: Where
is the negative gap penalty for insertions/deletions, is the negative mismatch penalty for substitutions and positive match score for the same symbol.
If we know the weight used when applying the algorithm, we can determine the final score of an alignment directly from the alignment itself by associating with each column its score and sum over all individual scores.
Gap penalties
There’s actually different models of gap penalties:
- Linear gap penalty: gap penalty for a single symbol is multiplied by the total length of a gap.
- Constant gap penalty: fixed negative score for the entire gap, regardless of its length.
- Affine gap penalty: combines the constant and linear approaches by defining a constant gap opening penalty and a linear gap extension penalty.
Substitution matrix
It’s possible to simplify the process using a substitution matrix. Given an alphabet
, the substitution matrix , which gives for every pair of symbols the weight of the substituting by in an alignment. The matrix is symmetrical. For
the weight represents the positive score assigned by a match. The usage of a substitution matrix changes the recursive computation to:
Local sequence alignment
Note
Let
and be two strings over the alphabet . Let also be a substitution matrix with scores for all and be a gap penalty. To find a two substrings that produce the alignment with the maximum possible score we use the Smith-Waterman algorithm. This algorithm uses the following computation: