Aller au contenu

DS 8 (MP2I 2021-2022) — Plus longue sous-suite commune

Devoir surveillé · MP2I · 2021-2022 · concours blanc · partie I du DS 8 (4 h au total)

Cours : Programmation dynamique

Autres parties : II. Graphes d'intervalles et coloration

Tout document ou dispositif électronique interdit.

Corrigé

Pas de corrigé disponible pour ce sujet.

Plus longue sous-suite commune

En biologie, il est souvent nécessaire de comparer l'ADN provenant d'organismes différents. Un brin d'ADN est une chaîne de molécules appelées bases, où les bases sont l'adénine, la guanine, la cytosine et la thymine. En représentant chaque base par son initiale, un brin d'ADN est une chaîne de caractères sur les lettres A, G, C et T.

Par exemple, un organisme peut avoir comme ADN la chaîne

\[ S_1 = \texttt{"ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"} \]

et un autre

\[ S_2 = \texttt{"GTCGTTCGGAATGCCGTTGCTCTGTAAA"} \]

Pour déterminer si deux organismes sont proches, il n'est pas suffisant d'observer les motifs contigus présents dans les deux chaînes car des mutations peuvent avoir modifié le brin en insérant des bases. Cependant, même dans ce cas, il doit être possible de retrouver une partie commune en supprimant des bases. On en déduit la définition suivante :

Définition

Soit \(s = "c_0 \dots c_{n-1}"\) une chaîne de caractères, une chaîne \(s'\) est une sous-chaîne de \(s\) s'il existe un \(p\)-uplet \((i_1, \dots, i_p)\) tel que \(s' = "c_{i_1} \dots c_{i_p}"\) et \(0 \le i_1 < i_2 < \dots < i_p \le n-1\).

Le problème qu'on se pose est de déterminer la plus longue sous-chaîne commune à deux chaînes. Ainsi, "GTCGTCGGAAGCCGGCCGAA" est la plus longue sous-chaîne commune à \(S_1\) et \(S_2\).

Caractérisation des plus longues sous-suites communes

Afin de simplifier la programmation d'une solution, on ne va pas s'intéresser à des chaînes de caractères mais à des suites finies d'éléments. On notera ici \((a_0,a_1,\dots,a_{n-1})\) une suite finie de \(n\) éléments. On adapte directement la notion précédente :

Définition

Soit \(A = (a_0, \dots ,a_{n-1})\) une suite finie et \(B\) une autre suite finie. On dit que \(B\) est une sous-suite de \(A\) s'il existe un \(p\)-uplet \((i_1, \dots, i_p)\) tel que \(B = (a_{i_1}, \dots, a_{i_p})\) et \(0 \le i_1 < i_2 < \dots < i_p \le n-1\).

Question 1

Si \(A\) est une suite finie de \(n\) éléments, combien comporte-t-elle de sous-suites ? Que penser d'un algorithme qui, pour déterminer une plus longue sous-suite commune entre \(A\) et \(B\), itère sur les sous-suites de \(A\) et teste si elles sont sous-suites de \(B\) ?

Soit \(A = (a_0, \dots, a_{n-1})\) et \(i \in \range{0}{n}\), on note \(A_i = (a_0, \dots, a_{i-1})\) le \(i\)-ème préfixe de \(A\). Par définition, \(A_0\) est la suite finie vide \(()\) et \(A_n = A\).

Question 2

Soient \(A = (a_0, \dots, a_{m-1})\) et \(B = (b_0, \dots, b_{n-1})\) deux suites finies et \(C = (c_0, \dots, c_{p-1})\) une plus longue sous-suite commune à \(A\) et \(B\).

Montrer que :

  1. Si \(a_{m-1} = b_{n-1}\) alors \(c_{p-1} = a_{m-1} = b_{n-1}\) et \(C_{p-1}\) est une plus longue sous-suite commune à \(A_{m-1}\) et \(B_{n-1}\).
  2. Si \(a_{m-1} \neq b_{n-1}\) alors \(c_{p-1} \neq a_{m-1}\) entraîne que \(C\) est une plus longue sous-suite commune à \(A_{m-1}\) et \(B\).
  3. Si \(a_{m-1} \neq b_{n-1}\) alors \(c_{p-1} \neq b_{n-1}\) entraîne que \(C\) est une plus longue sous-suite commune à \(A\) et \(B_{n-1}\).

Équation de récurrence

On considère ici deux suites \(A = (a_0, \dots, a_{m-1})\) et \(B = (b_0, \dots, b_{n-1})\) et, pour \(i \in \range{0}{m}\) et \(j \in \range{0}{n}\), on note \(f(i,j)\) la longueur d'une plus grande sous-suite commune à \(A_i\) et \(B_j\).

Question 3

  1. Calculer \(f(i,j)\) quand \(i = 0\) ou \(j = 0\).
  2. On suppose que \(i, j > 0\) et \(a_{i-1} = b_{j-1}\). Justifier que \(f(i,j) = 1 + f(i-1, j-1)\).
  3. On suppose que \(i, j > 0\) et \(a_{i-1} \neq b_{j-1}\). Justifier que \(f(i,j) = \max(f(i, j-1),f(i-1,j))\).

Résolution de la récurrence

On va résoudre la récurrence en OCaml ici.

Les sous-suites sont ainsi représentées par des 'a array.

Question 4

Écrire une fonction naïve longueur_sous_suite de signature

'a array -> 'a array -> int -> int -> int

telle que l'appel à longueur_sous_suite a b i j renvoie la valeur de \(f(i,j)\) pour les suites données par \(a\) et \(b\).

On rappelle l'existence des fonctions suivantes :

  • Hashtbl.create n qui crée une table de hachage de taille initiale \(n\).
  • Hashtbl.find t c qui renvoie la valeur associée à la clé c dans la table et produit l'exception Not_found s'il n'y en a pas.
  • Hashtbl.add t c v qui rajoute une correspondance entre la clé c et la valeur v.

Question 5

Écrire une version mémoïsée de la fonction précédente.

On pourra, au choix, créer un cache en dehors de la fonction ou dans la fonction elle-même.

Tabulation

On va considérer ici une version tabulée en C.

On va représenter \(f\) dans une matrice de dimension \((m+1) \times (n+1)\). Pour simplifier, on peut considérer un tableau M de \((m+1)(n+1)\) entiers où on place \(f(i,j)\) dans M[j * (m+1) + i].

Question 6

Déterminer un ordre de remplissage de \(M\) qui soit compatible avec la relation de récurrence établie au paragraphe précédent.

Question 7

Écrire une fonction de prototype

int longueur_sous_suite(int *a, int m, int *b, int n);

qui renvoie la longueur d'une plus longue sous-suite commune aux deux tableaux d'entiers a de longueur m et b de longueur n.

On utilisera une tabulation selon le principe qui vient d'être exposé.