Programmation dynamique

Etape 1: Remplissage de la matrice

On veut aligner les séquences CADBD et ACBCDB.

La matrice de scores ci-dessous est remplie par:

 
v ([0->i], [0->j]) =
max { 
  v ([0->i-1], [0->j-1]) + v ([i],[j])
  v ([0->i-1], [0->j  ]) + v ([i],[-])
  v ([0->i  ], [0->j-1]) + v ([-],[j])
}

 
Avec par exemple:
v ([],[])=0
v ([-],[])=-1
v ([x],[y])=-1 (x different de y)
v ([x],[x])=+2

Par ex. l'entrée {4,1} (colorée) est obtenue par max (-3+2, 0-1, -4-1), c'est à dire -1.

Etape 2: Reconstitution de l'alignement

Le chemin (alignement) optimal ci-dessus est déterminé par l'algorithme:

• en partant de la cellule (m,n), retrouver quelle cellule était responsable de la cellule courante (chemin suivi représenté par les traits rouges).
• 3 Solutions:

acbcdb- 
-c-adbd 

acbcdb- 
-ca-dbd 

-acbcdb
cadb-d-

Exemple tiré du cours Bioinformatics & Computational Genomics du Weizmann Institute