==========================
Idée générale:

initialisation
for i=1 to n
    for j=1 to n
        calculer V(i,j)
        calculer W(i,j)
        calculer S(i,j)
    end
end
===========================

Les matrices V et W sont initialisées à une très grande valeur négative, et dans le code Python à -float('inf').

Quant à la matrice S, qui contiendra le résultat final, elle est initialisée à 0, sauf les premières ligne et colonne, qui contiennent les résultats de la fonction de la pénalité affine pour chaque case.

La plus simple de ces fonctions est la pénalité affine: soit n la longueur d'un trou, alors:

affinePenalty(n)=C+(n−1)∗E, en supposant C,E<0.

============================

for i in range(1,firstSequenceLength+1) :
    for j in range(1,secondSequenceLength+1) :

        V[i][j] = max(S[i-1][j] + startingGapPenalty + extensionPenalty, \
                      V[i-1][j] + extensionPenalty)

        W[i][j] = max(S[i][j-1] + startingGapPenalty + extensionPenalty , \
                      W[i][j-1] + extensionPenalty)

        score = substitutionMatrix.getScore(firstSequence[i-1], secondSequence[j-1])

        S[i][j] = max(V[i][j], W[i][j], S[i-1][j-1] + score)