The algorithm is very simple. One writes the first sequence across the top of a grid or matrix and the other sequence down the left hand side. A scoring scheme is then required. This can be a simple identity scheme in which a match scores 2 and a mismatch scores 0 or a more complex scheme where a different score is given when each of the 20 amino acids replaces any one of the other 20 amino acids (i.e. 20x20 = 400 scores). The "Dayhoff Mutation Matrix" (Dayhoff et al., 1978, "A model of evolutionary change in proteins" in Atlas of Protein Sequence and Structure 5 Suppl 3, 345-353 (National Biomedical Research Foundation, Silver Spring, Washington DC) is one commonly used mutation scoring matrix.
Scores are filled into the matrix starting in the bottom right hand corner using the following formula:
This simply means that the score for cell i,j (Si,j) is the score that one gets from the residue match scoring scheme (si,j) plus the maximum of three pre-existing scores: (1) the score in the diagonal cell, (2) the maximum score in the cells below the diagonal, (3) the maximum score in the cells to the right of the diagonal. If one of the latter "off-diagonal" scores is used then a length-dependent "gap-penalty" is also applied.
