Download Sequence Alignment Algorithms

Figure 1: The basic principle of sequence alignment is demonstrated in the above illustration.
For simplicity, two short fragments are aligned with one superimposed on the other. Some of the
possible ways of aligning the reference and the query are shown. The score of each pair of
sequences is calculated based on the scoring scheme provided for this alignment. It appears that
the first alignment achieved the highest final score of 0 with 3 matches, 2 mismatches, 1 gap, and
2 transversion mutations (Lesk, 2002).
Most nucleotide sequence alignment algorithms refer to a scoring matrix to score a
particular alignment of sequences (Lesk, 2002). The matrix is filled based on the scoring
parameters that were set for the algorithm. The algorithm will then proceed with the
search for the best alignment by tracking a path along the matrix that produces the
highest score. Figure 2 below shows a scoring matrix that outlines a random scoring
scheme for simple substitution mutations. Here, the diagonal path exhibits the highest
score, meaning that aligning ATCG on top of ATCG will be the best alignment.
A
T
C
G
A
20
10
5
5
T
10
20
5
5
C
5
5
20
10
G
5
5
10
20
Figure 2. A substitution scoring matrix (Lesk, 2002).
The scoring scheme of different algorithms may be modified depending on the type of
alignment that the algorithm is designed to compute. Users are recommended to get
familiarized with the algorithms so they can select the most appropriate algorithm to
carry out the type of alignment that they want, generating the most ideal results suitable
for their purposes.
10