Thèmes :
• Algorithmique : paradigme de la programmation dynamique
• Programmation
Difficulté :
• Algorithmique : moyen

• Programmation : facile
Introduction :
Les séquences d'ADN sont des mots (de courts à très très longs suivant les espèces!) écrits
avec quatre lettres : A, C, G et T. Pour comparer deux espèces entre elles, on peut rechercher
à quel point elles se ressemblent et pour cela chercher à mesurer à quel point leur séquence
d'ADN se ressemblent. En première approximation, on peut mesurer la ressemblance entre
deux séquences d'ADN par le nombre maximum de lettres qu'elles ont en commun dans le
même ordre. Par exemple,
Par exemple, si les séquences de deux espèces sont :
• Espèce 1 : ACGTACTGTACTGACGACGAT
• Espèce 2 : ACTAGCATABACGACGAT
• Alors, une plus grande sous-chaîne commune entre les deux espèces est
ACTAGCTACGACGAT
Sous-chaîne commune de longueur maximale :
Pour calculer le nombre maximum de lettres en commun entre deux chaînes de caractères u et
v de longueurs n et* m respectivement, nous allons utiliser un tableau opt de taille (n+1) x
(m+1) où
opt[i][j] = le nombre maximum de lettres en commun et dans le même ordre entre
les i premières lettres de u et les j premières lettres de v

Clairement,
opt[0][j] = 0 pour tout 0 ≤ j ≤ m, et
opt[i][0] = 0 pour tout 0 ≤ i ≤ n.
De plus, on peut démontrer que : pour 1 < i ≤ n et 1 ≤ j ≤ m,

[ 1 + opt[i-1][j-1] si u[i-1] = v[j-1] # on utilise la lettre en commun aux positions i et j de

u et v
opt[i][j] = MAX [ opt[i-1][j] # on utilise pas la i-ème lettre de u
[ opt[i][j-1] # on n'utilise pas la j-ème lettre de v
Question : Démontrer cette équation est correcte. (On pourra étudier deux cas suivant si le

ième caractère de u et le jème caractère de v sont utilisés à la même position dans une sous-
chaine commune de longueur maximale ou non, et remarquer que les préfixe et suffixe de cette

sous-chaîne de longueur maximale avant et après cette position doivent être des sous-chaînes
communes de longueur maximale des préfixe et suffixe de u et v avant et après ces positions)
On peut donc utiliser cette équation pour remplir de proche en proche le tableau opt.

u\v A C T A G C A T A B A C G A C G A T
A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
C 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
G 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
T 0 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3
A 0 1 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
C 0 1 2 3 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5
T 0 1 2 3 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6
G 0 1 2 3 4 4 5 5 6 6 6 6 6 6 6 6 6 6 7
T 0 1 2 3 4 5 5 5 6 6 6 6 6 7 7 7 7 7 7
A 0 1 2 3 4 5 5 5 6 6 6 6 6 7 7 7 7 7 8
C 0 1 2 3 4 5 5 6 6 7 7 7 7 7 8 8 8 8 8
T 0 1 2 3 4 5 6 6 6 7 7 7 8 8 8 9 9 9 9
G 0 1 2 3 4 5 6 6 7 7 7 7 8 8 8 9 9 9 10

A 0 1 2 3 4 5 6 6 7 7 7 7 8 9 9 9 10 10 10
C 0 1 2 3 4 5 6 7 7 8 8 8 8 9 10 10 10 11 11
G 0 1 2 3 4 5 6 7 7 8 8 8 9 9 10 11 11 11 11
A 0 1 2 3 4 5 6 7 7 8 8 8 9 10 10 11 12 12 12
C 0 1 2 3 4 5 6 7 7 8 8 9 9 10 11 11 12 13 13
G 0 1 2 3 4 5 6 7 7 8 8 9 10 10 11 12 12 13 13
A 0 1 2 3 4 5 6 7 7 8 8 9 10 11 11 12 13 13 13
T 0 1 2 3 4 5 6 7 7 8 8 9 10 11 12 12 13 14 14
0 1 2 3 4 5 6 7 8 8 8 9 10 11 12 12 13 14 15

Question : Écrire un programme qui remplit le tableau opt pour deux chaînes de caractères u et
v.
Question : Comment utiliser le tableau opt pour retrouver une sous-chaîne commune de
longueur maximum entre u et v ? On pourra chercher à construire simultanément avec opt, un
tableau prec de taille (n+1) x (m+1) tel que prec[i][j] = (i-1, j-1), (i-1, j) ou (i, j-1) suivant si
opt[i][j] = 1+opt[i-1][j-1] ou opt[i-1][j] ou opt[i][j-1]. Démontrer que l'on peut associer une
lettre d'une plus longue sous-chaine commune chaque fois que prec[i][j] = (i-1, j-1) et
donc reconstituer une plus longue sous-chaine commune en partant de la case (n, m) et en
remontant en utilisant le tableau prec[i][j] jusqu'à une case (0,j) ou (i,0).
Question : (avancée) Comment retrouver toutes les plus longues sous-chaines communes
entre u et v à partir du tableau opt ?
Question : (avancée++) Proposer une structure compacte (sous forme d'un graphe) pour les
représenter en mémoire. (On pourra mémoriser pour chaque case (i, j) la liste des (k,l) ∈ {(i-1,
j-1), (i-1, j), (i, j-1)} tels que opt[i][j] = 1+opt[k][l] si (k, l) = (i-1, j-1) ou opt[i][j] = opt[k]
[l] sinon, puis chercher à compacter cette structure)
Application à la philogénie (avancé) :
Le problème de la philogénie est de reconstituer l'histoire des liens entre les différentes
espèces. Les séquences ADN sont des outils précieux dans cette démarche. Nous proposons
ici une première approche très simplifiée de ce problème.
On considère le problème suivant : étant données n chaînes de caractères, on cherche à les
organiser sous la forme d'un arbre binaire à n feuilles dont les nœuds seront étiquetés par des
chaînes de caractères ; les étiquettes des n feuilles devront être les n chaînes en entrée et les
étiquettes des nœuds internes seront des plus longues sous-chaines communes aux feuilles du
sous-arbre correspondant. Nous cherchons à obtenir le ``meilleur arbre possible. Nous
proposons l'heuristique suivante (c'est-à-dire un algorithme ``raisonnable et intuitif mais dont on
ne maîtrise pas la qualité de la solution produite): on commence avec n arbres réduits à un
unique nœud étiquetés par chacune des n chaînes
• Tant qu'il y a plusieurs arbres :
• Considérer les étiquettes des racines des arbres

• Calculer pour chaque paire de ces étiquettes, la longueur maximale d'une sous-
chaine commune

• Choisir une paire d'étiquette pour laquelle cette longueur est maximale, créer un
nouvel arbre dont les deux fils seront les deux arbres correspondants et étiqueter
la racine par une sous-chaîne commune de longueur maximale de ces deux
chaînes.

• Renvoyer l'unique arbre restant
Question : (avancée) Implémenter cet algorithme et tester-le sur différents exemples. Tester
l'influence du choix de la sous-chaine de longueur maximale pour étiqueter la racine (il en existe
plusieurs, laquelle choisir ? Quelle influence cela a-t-il ?)
Question : (avancée++) Comment feriez-vous pour étiqueter les arbres par une plus longue
sous-chaine commune à toutes les chaines aux feuilles de l'arbre ? Proposer une généralisation
de l'algorithme ci-dessus au cas de k chaînes qui utilisera un tableau de à k dimensions (au lieu
de 2) et de taille le produit des longueurs des chaînes. Modifier l'algorithme de philogénie pour

incorporer cette variante et comparer les résultats.