Le problème de l'alignement de séquences consiste, dans la version qui nous intéresse ici, à rechercher la plus longue sous-chaîne commune.
C'est un problème utile en génétique, aussi notre alphabet sera composé des lettres : {A; C; T; G} qui représentera les bases nucléiques : Adénine, Cytosine, Thymine et Guanine qui composent l'ADN.
Nous avons deux mots :
Dans ce cas, il existe différentes sous_chaînes de longueur maximale, par exempple, nous avons la chaîne de longueur 7 "𝐴𝑇𝐴𝐶𝐴𝐶𝐴" :
On notera par la suite plscc(mot_1, mot_2) l'ensemble des plus longues sous-chaînes de mot_1 et mot_2. Et
longueur_plscc(mot_1, mot_2) la longueur des plus longues sous-chaînes de mot_1 et mot_2.
Résolution du problème¶
On s'intéressera dans un premier temps au problème qui consiste à déterminer la longueur de la plus longue sous-chaîne commune.
Avant de résoudre ce problème en utilisant Python, il faut définir un ou plusieurs sous-problèmes qui nous permettront de résoudre le problème global (qui consiste à déterminer la longueur de la sous-chaîne la plus longue). C'est la partie la plus difficile.
On peut distinguer deux cas :
- Cas 1, Les deux mots ont la même dernière lettre A
mot_1 = mot1gaucheA et mot_2 = mot2gaucheA. Alors, on va prendre la taille de la sous chaîne commune de mot1gauche et mot2gauche à laquelle on va ajouter 1 : longueur_plscc(mot_1, mot_2) = longueur_plscc(mot1gauche, mot2gauche) + 1 - Cas 2, Les deux mots n'ont pas la même dernière lettre : mot1 = mot1gaucheA et mot_2 = mot2gaucheB. On ne peut pas aligner la lettre A et la lettre B et on doit alors chercher la plus longue sous-chaîne commune entre
plscc(mot_1, mot2gauche)et )plscc(mot_2, mot1gauche))car on pourrait trouver un A dans mot2gauche ou un B dans mot1gauche.
Dit autrement, cela revient à longueur_plscc(mot_1, mot_2) = max(longueur_plscc(mot_1, mot2gauche), longueur_plscc(mot_2, mot1gauche))
Programmation¶
Calcul de la longueur d’une plus longue sous-chaîne commune¶
On va construire une matrice longueur, telle que longueur[i][j] représente la longueur de la plus longue sous chaîne commune entre mot_1[:i] et mot_2[:j] (indices i et j inclus).
Il faut faire attention à l’initialisation de cette matrice, c’est-à-dire aux valeurs à donner à longueur[i][0] (ou bien, de la même façon, à longueur[0][j]). En effet, on ne peut pas, quand 𝑖 (ou 𝑗) vaut 0, utiliser l’indice 𝑖 − 1 (ou 𝑗 − 1) car une des chaînes est de longeur nulle. Dans notre cas les indices i à 0 et les indices j à 0 vont représenter le fait qu'une des sous chaînes est vide.
On aura donc une ligne et une colonne en plus qui ne contiendra que des zéros.
- Compléter la fonction récursive
def rec_longueur_plscc(mot_1, mot_2)qui calcule l’ensemble des valeurs de la matrice longueur.
def rec_longueur_plscc(mot_1, mot_2):
if len(mot_1) == 0 or len(mot_2) == 0:
return COMPLETER
elif mot_1[-1] == mot_2[-1]:
return COMPLETER
else:
return COMPLETER
def longueur_plscc(mot_1, mot_2) qui calcule l’ensemble des valeurs de la matrice longueur.
def longueur_plscc(mot_1, mot_2):
longeur_max = [ [0 for lettre in range(len(mot_1) + 1)] for lettre in range(len(mot_2) + 1)]
for i in range(len(mot_1) + 1):
for j in range(len(mot_2) + 1):
if i == 0 or j == 0:
COMPLETER
elif mot_1[i-1] == mot_2[j-1]:
COMPLETER
else:
COMPLETER
return COMPLETER
- Tester vos fonctions sur l’exemple précédent ainsi que sur d’autres exemples pertinents. On gardera trace de ces tests dans le programme.