TP - Alignement de Séquences☘
Le problème de l'alignement des séquences se pose dans de nombreux domaines scientifiques. Ce TP a pour but de vous faire programmer une solution à ce problème au moyen du paradigme de programmation dynamique dans sa version « Bottom-Up ».
Conseil
Il est conseillé de se munir des résultats du TD effectué en classe.
Téléchargez le fichier « à trous » : TPE03.30.py
(clic droit -> [Enregistrer sous]) et enregistrez-le dans le répertoire
[E03-Prog_Dynamique].
Illustration dans un cas particulier☘
Remerciements
Ce paragraphe a été rédigé par L. Fasquelle, enseignant au Lycée de La Plaine de l'Ain. Qu'il en suit ici remercié.
Les initiales ADN signifient « acide désoxyribonucléique ». L'ADN constitue la molécule support de l'information génétique héréditaire.
L'ADN est une molécule très longue, composée d'une succession de nucléotides. Il existe quatre nucléotides différents : l'adénosine (A), la cytidine (C), la guanosine (G) et la thymidine (T), dont l'ordre d'enchaînement est très précis et correspond à l'information génétique.
En bio-informatique, l'alignement de séquences est une manière de représenter deux ou plusieurs séquences de macromolécules biologiques (ADN, ARN ou protéines) les unes sous les autres, de manière à en faire ressortir les régions homologues ou similaires.
L'objectif de l'alignement est de disposer les composants aminés pour identifier les zones de concordance. Ces alignements sont réalisés par des programmes informatiques dont l'objectif est de maximiser le nombre de coïncidences entre nucléotides ou acides aminés dans les différentes séquences.
Ceci nécessite en général l'introduction de « trous » à certaines positions dans les séquences, de manière à aligner les caractères communs sur des colonnes successives.
Au cours de l'évolution, des nucléotides ou des acides aminés ont pu s’insérer
ou au contraire disparaître. Pour tenir compte de ces insertions ou délétions
éventuelles, il faut introduire un caractère particulier, appelé gap et noté
« — » ou « ~ ». La mise en correspondance d’un caractère d’une séquence
avec un gap dans l’autre séquence s’interprète :
- soit comme une insertion du caractère dans la première séquence
- soit comme une délétion d’un caractère dans la seconde.
Exemple
- Les séquences en (a) sont peu similaires si comparées sur toute leur longueur : 6 caractères différents
- En (b), un simple décalage d’un caractère augmente la valeur de similarité : 2 caractères différents seulement.
À partir de l'identification de similarités entre la séquence d'une première protéine dont on connaît le mécanisme d'action et celle d'une deuxième protéine dont on ne connaît pas le mécanisme de fonctionnement, on peut déduire des similarités sur la séquence non connue et proposer de vérifier de manière expérimentale ces déductions.
Partie 1 - Construction du tableau des scores☘
Comme nous l'avons vu en TD, et afin de préparer au mieux l'étape d'alignement
de séquences, nous allons effectuer une modification du tableau des scores
en insérant, en première ligne et en première colonne, le cas du caractère
« ~ », c'est-à-dire du trou.
Exemple
Avec les mots LIVRE et OLIVIERS, on souhaite obtenir le tableau
suivant :
| ~ | O | L | I | V | I | E | R | S | |
|---|---|---|---|---|---|---|---|---|---|
| ~ | 0 | -1 | -2 | -3 | -4 | -5 | -6 | -7 | -8 |
| L | -1 | -1 | 0 | -1 | -2 | -3 | -4 | -5 | -6 |
| I | -2 | -2 | -1 | 1 | 0 | -1 | -2 | -3 | -4 |
| V | -3 | -3 | -2 | 0 | 2 | 1 | 0 | -1 | -2 |
| R | -4 | -4 | -3 | -1 | 1 | 1 | 0 | 1 | 0 |
| E | -5 | -5 | -4 | -2 | 0 | 0 | 2 | 1 | 0 |
Ce tableau est obtenu par la relation de récurrence :
-
Complétez la définition de la fonction
tab_align()qui doit renvoyer le tableau 2D présenté ci-dessus.
Plusieurs pistes peuvent vous aider. On rappelle de plus quemot1représente le mot qui sera écrit « verticalement ».1 2 3 4 5 6
def tab_align(mot1, mot2): """ mot1, mots2 - str, chaînes de caractères à aligner (même casse) Sortie: list - tableau de tableaux donnant le score d'alignement caractère par caractère (+1 pour bien alignés, -1 sinon) """Piste n°1
Pour prendre en compte le caractère
'~', insérez-le devant chacune des chaînes de caractèresmot1etmot2.Piste n°2
Initialisez le tableau des scores puis remplissez les première ligne et la première colonne.
Piste n°3
Parcourez chacune des cases restantes du tableau et remplissez-la à l'aide de la relation de récurrence.
-
Testez votre fonction à l'aide des deux propositions ci-dessous :
>>> tab_align("LIVRE", "OLIVIERS") [[0, -1, -2, -3, -4, -5, -6, -7, -8], [-1, -1, 0, -1, -2, -3, -4, -5, -6], [-2, -2, -1, 1, 0, -1, -2, -3, -4], [-3, -3, -2, 0, 2, 1, 0, -1, -2], [-4, -4, -3, -1, 1, 1, 0, 1, 0], [-5, -5, -4, -2, 0, 0, 2, 1, 0]] >>> tab_align("TEMPLE", "REFLET") [[0, -1, -2, -3, -4, -5, -6], [-1, -1, -2, -3, -4, -5, -4], [-2, -2, 0, -1, -2, -3, -4], [-3, -3, -1, -1, -2, -3, -4], [-4, -4, -2, -2, -2, -3, -4], [-5, -5, -3, -3, -1, -2, -3], [-6, -6, -4, -4, -2, 0, -1]] -
Cette question est optionnelle, à ne traiter que si vous êtes en avance.
Pour mieux visaliser le tableau obtenu, complétez la définition de la fonctionaffichage_tab_mots().
Utilisez le test ci-dessous pour adapter cet affichage.Test d'affichage
>>> affichage_tab_mots("LIVRE", "OLIVIERS") ~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0
Partie 2 - Construction de l'alignement☘
A partir de la dernière case du tableau de score et à partir des caractères des deux mots passés en paramètres, vous allez reconstruire deux chaînes de caractères de même longueur comportant éventuellement des trous et qui s'aligneront selon le score maximum. Il existe plusieurs cas à prendre en compte.
On désigne par mot1 et mot2 les mots à aligner, et par result1 et
result2 les chaînes de caractères obtenues (avec des trous éventuels)
pour l'alignement de mot1 et mot2.
Répondez aux questions sur votre cahier puis appelez l'enseignant avant de passer à la programmation.
Remarque importante
Les tableaux sont là pour illustrer chaque question au moyen d'un exemple, mais c'est une réponse dans le cas général qui est attendue à chaque fois.
-
Que se passe-t-il si on aboutit à la première case ?
~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 -
Vous vous trouvez sur une case de la première ligne, de coordonnées
(0, j).~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
Vous vous trouvez sur une case de la première colonne, de coordonnées
(i, 0).~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
Vous vous trouvez sur une case quelconque, de coordonnées
(i, j).-
Pourquoi faut-il s'intéresser à la valeur des cases à gauche, en haut et haut-gauche de cette case ?
-
La case
(i, j)contient le plus grand score parmi les quatre :~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
La case
(i, j-1)contient le plus grand score parmi les quatre :~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
La case
(i-1, j)contient le plus grand score parmi les quatre :~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
La case
(i-1, j-1)contient le plus grand score parmi les quatre :~ O L I V I E R S ~ 0 -1 -2 -3 -4 -5 -6 -7 -8 L -1 -1 0 -1 -2 -3 -4 -5 -6 I -2 -2 -1 1 0 -1 -2 -3 -4 V -3 -3 -2 0 2 1 0 -1 -2 R -4 -4 -3 -1 1 1 0 1 0 E -5 -5 -4 -2 0 0 2 1 0 - Sur quelle case vous trouverez-vous ensuite ?
- Que peut-on en déduire pour
result1etresult2?
-
Comment faire si plusieurs de ces cases contiennent un score maximum ?
-
-
Appelez l'enseignant pour qu'il vérifie vos réponses aux questions précédentes.
-
Complétez la définition de la fonction
construire_alignement()qui doit renvoyer les deux chaînes de caractères passées en paramètre, éventuellement complétés par des trous, de sorte qu'elles aient la même longueur et maximisent le score d'alignement.
Plusieurs pistes peuvent vous aider.1 2 3 4 5 6 7 8 9
def construire_alignement(mot1, mot2): """ mot1, mots2 - str, chaînes de caractères à aligner (même casse) Sortie: tuple - couple de chaînes de caractères de même longueur. La première est constituée des caractères de mot1 La seconde est constituée des caractères de mot2 Dans les deux cas, des trous permettant l'alignement optimal sont symbolisé par le caractère "~" """Piste n°1
Pour prendre en compte le caractère
'~', insérez-le devant chacune des chaînes de caractèresmot1etmot2.Piste n°2
Vous partez de la dernière case du tableau, quelles sont ses coordonnées ?
Piste n°3
Remontez ensuite le tableau grâce à l'algorithme mis en place dans les questions précédentes. Construisez caractère par caractère le contenu des chaînes à renvoyer.
-
Testez votre fonction à l'aide des deux propositions ci-dessous :
>>> result1, result2 = construire_alignement("LIVRE", "OLIVIERS") >>> print(f"{result1}\n{result2}") ~LIVRE~~ OLIVIERS >>> result1, result2 = construire_alignement("ACTTGCATT", "AACTTGCAT") >>> print(f"{result1}\n{result2}") A~CTTGCATT AACTTGCAT~