9.3.1 Step 1: define a scoring scheme

A scoring scheme is first defined, and then the dynamic scoring is done, starting from the top left to the bottom right of the matrix:

• Match score (S_ij) = 2
• Mismatch score (S_ij) = –1
• Gap penalty (d) = –2

Here, “i” (varying from 1, 2, …, m) and “j” (varying from 1, 2, …, n) refer to the indexes for the row and column numbers, respectively, of the cell of the scoring matrix (described in Step 2). Please note that the scoring scheme can differ according to the evolutionary relatedness of the input sequences. A gap extension penalty is also introduced in advanced methods of such dynamic algorithms, to direct proper alignment and select the best one, based on the scores.

9.3.2 Step 2: initiation of matrix construction

This step starts with creating a matrix that represents the score for each pair of residues belonging to the pair of sequences.

1. Seq1: written along the vertical axis (or Y‐axis) of the matrix (i.e., along the rows).
2. Seq2: written along the horizontal axis (or X‐axis) of the matrix (i.e., along the columns).

Finally, we will get a matrix with each of its cells filled up with three scores obtained from three different types of movements, as shown below:

• Horizontal movement: represents a gap in the sequence written vertically (along the Y‐axis, row numbers have been denoted by “i”)
• Vertical movement: represents a gap in the sequence written horizontally (along the X‐axis, column numbers are indicated by “j”)
• Diagonal movement: representing either match or mismatch between the two sequences (cell positions indexed by “i” and “j”, respectively) (Figure 9.1).

Annex one row at the top and one column at the left of the original m × n dimensional matrix (to make it an (m + 1) × (n + 1) dimensional matrix). These are termed the 0th row and 0th column, respectively. Next, fill the first cell (i.e., the cell located at the top left‐most corner of the 0th row and 0th column) with a zero.

9.3.2.1 Scoring method: dynamic programming

The score of each cell can be determined from three different movements towards the cell. The formula used to calculate the scores for each cell is shown in Figure 9.2.

[9.1]

Select the highest score(s): Now, after obtaining these three scores in the cell being studied, the highest value is selected, which is to be used as the score of that cell. This highest score is used for calculating the respective scores of the cells located just right (hence, pertaining to horizontal movement), just bottom (vertical movement) and just at the bottom‐right (diagonal movement) positions of the current cell. If more than one score shows the highest value, then that highest value will be considered for calculating the score of the adjacent cells. However, the backtracking will be through all these cells contributing to the same highest values (see Figures 9.3 and 9.4).

Let us clarify this with the first few cells of the matrix shown in Step 3:

1. Put “0” value in the first cell (utmost top left cell).
2. The value of the next cell (right side) will be 0 + (–2) = –2; since it is a horizontal movement, so the gap penalty of –2 will be given. The next cell at the right side will have the score of –2 + (–2) = –4, due to the gap penalty for the same horizontal movement. Likewise, the subsequent cells on the right side will be awarded –6, –8, –10, –12, –14, –16, and the last one –18.
3. Now, for the downward movement in the very first column, the gap penalty will be consecutively awarded to each cell. The cells will have the scores of –2, –4, … –14.
4. The diagonal movement starts from 0 to the bottom right cell; we will check whether there is a match or mismatch. In this case, there is a match of “C” to “C”. Hence, a score of +2 will be awarded.
5. Please note that, except for the first row and first column (which were annexed to the original matrix), every cell of the matrix can have three values, due to three possible movements towards that cell:
   • vertical movement from the cell just above,
   • horizontal movement from the cell just at left, and
   • diagonal movement from the adjacent cell just at the top‐left position).
   In the following matrix, three colors have been used: Blue for vertical movement (Gap), Yellow highlight for diagonal movement (Match or Mismatch), and Red for horizontal movement (Gap).
6. Now, out of these three values, the highest one will be selected as the score for that cell. The chosen score(s) has/have been highlighted in yellow in the matrix below.

9.3.3 Step 3: trace‐back step

Finally, the trace‐back step starts from the last cell at the right side of the bottom row in a way such that arrow(s) will be drawn to the cell(s) from which the current score (highest of three scores of the present cell) has been obtained. If there are two or three cells which contribute to the highest value, then two (or three, respectively) arrows will be drawn to indicate the previous cells.

The arrows are drawn from the bottom right cell towards the top left cell. If certain cell(s) have more than one arrow, this will lead to more than one path at every such junction.

Tracing back is done from the bottom right cell towards the top left cell. The path is determined based on the source of the cell which contributes to the highest score in the present cell.

The dynamic programming thus proceeds from one cell to the other (in the defined directions), until the whole matrix obtains the score for each of the cells.

All possible paths are obtained from the scoring matrix during the process of global alignment.

9.3.4 Step 4: calculating the scores for each alignment

The score for each of these alignments is calculated according to the scoring scheme set at the beginning of scoring. The alignment score with the highest value is considered as the best global alignment. One could get more than one highest score (same value) when there are multiple (more than one) pair‐wise alignments. In such a situation, all those alignments with the highest score are equally good, and any one of these can be accepted as the global alignment.

In the example shown above, we get seven possible global alignments, all of which have the highest score (i.e., equal to 4). Here, we can select any one of these alignments as the best alignment (Figure 9.5).