Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ==========================
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement