Qu’est-ce qui distingue la programmation dynamique (DP) de l’approche « diviser pour régner » (DR) ? Nous complétons cette introduction par l’étude d’un problème typique de DP, l’alignement de séquences.
I. Historique et concepts de la programmation dynamique
La « programmation dynamique », DP, reprend l’approche inductive de DR qui résout un problème à partir de la résolution de problèmes de taille inférieure.
L’approche DP permet la réutilisation de sous-problèmes sans refaire les calculs, tandis que dans l’approche DR typique, comme le tri fusion, les sous-problèmes sont totalement indépendants.
De nombreux problèmes classiques relèvent de l’approche DP, comme la recherche de la plus longue sous-séquence commune à deux séquences, le problème du sac à dos ou celui de l’alignement des séquences.
II. L’alignement des séquences
1) Notion de séquence
Une séquence est une suite finie de symboles dans un alphabet, par exemple une suite de chiffres (entre 0 et 9) ou de lettres (entre a et z). Les chaînes "CTTGGG" et "TCGAA" sont des séquences sur l’alphabet A,C,G,T souvent utilisé en bio-informatique. La chaîne "00110101" est une séquence sur l’alphabet 0,1.
Une sous-séquence est une suite de lettres, non nécessairement contiguës, d’une séquence, qui en respecte l’ordre. Les chaînes uir et unr sont ainsi des sous-séquences de butiner. On note |w| la longueur de la séquence w.
2) Présentation du problème
Le problème de l’alignement des séquences est important pour explorer la similarité de codes génétiques ou dans les moteurs de recherche.
Pour représenter tous les alignements possibles, on introduit un espace désigné sous le nom de gap et noté ~.
Voici deux alignements possibles pour les chaînes ocurrance et occurrence :
3) Scores et définitions
Dans cet exemple, attribuons des scores en fonction de la qualité de l’alignement. Nous choisissons de compter 6 points en cas de correspondance des lettres, –3 points pour un alignement entre le gap et n’importe quelle lettre et –1 point pour un mauvais alignement (entre deux lettres différentes).
Le score de similarité est alors pour Alignement 1 : 8×6−3−1=44 et pour Alignement 2 : 8×6−3×3=39.
De manière générale, on définit une fonction de similarité p entre couples de lettres par : p(a,a) = m, p(a,b) = k si a ≠ b et p(a,~) = g où m, k et g sont des entiers. Ici on a pris m = 6, k = -1 et g = -3.
On appelle alignement de x et y, un couple de mots x' et y' sur l’alphabet de départ augmenté du caractère spécial ~ vérifiant |x'| = |y'| et tel que la suppression de ~ dans x' donne x et la suppression de ~ dans y' donne y, et tel que les gaps ~ ne se retrouvent pas alignés dans x' et y'.
On se donne une fonction de similarité p et on définit le score d’un alignement par :
score(x', y')=∑i=1np(x'i,y'i)
où n est la longueur commune à x' et y' et les x'i et y'i sont les lettres de x' et y'.
4) Recherche du meilleur score
Remarquons que si on part de 2 mots x et y, et qu’on ajoute la lettre a à x et la lettre b à y, le meilleur alignement de xa et yb peut s’obtenir de 3 façons possibles : en alignant a et b, en alignant xa et y en plaçant un gap face à b ou en alignant x et yb en plaçant un gap face à a.
On en déduit la formule d’induction suivante : la fonction qui calcule le meilleur score d’alignement possible entre x et y, notée mas(), va calculer à chaque étape le score le plus favorable parmi ces 3 alternatives et choisir ainsi la meilleure.
Plus précisément on note mas(x,y,i,j) le score du meilleur alignement entre x1x2x3…xi et y1y2y3…yj et p la fonction de similarité entre lettres.
Par convention, on pose mas(x,y,0,j) = g*j où g, un entier négatif, est le score attaché à un gap (cette colonne j correspond donc dans ce cas à l’une des séquences composée uniquement de gaps) et de même on prend mas(x,y,i,0) = g*i.
Notre induction traduit la remarque initiale avec 3 possibilités d’alignement et leurs scores respectifs :
Le calcul de mas est au minimum en O(nm), en raison de la double boucle sur i et j. L’occupation mémoire est aussi en O(nm).