Aller au contenu

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.

Séquence d'ADN - Insuline

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 :

score(i, j) = \left\{ \begin{array}{ll} 1+score(i-1, j-1) & si \; mot1[i] = mot2[j] \\ -1+max \left( score(i-1, j-1) ; score(i, j-1) ; score(i-1, j) \right) & sinon \\ \end{array} \right.
  1. 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 que mot1 repré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ères mot1 et mot2.

    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.

  2. 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]]
    
  3. 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 fonction affichage_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.

  1. 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

  2. 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

    1. Sur quelle case vous trouverez-vous ensuite ?
    2. Que peut-on en déduire pour result1 et result2 ?
  3. 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

    1. Sur quelle case vous trouverez-vous ensuite ?
    2. Que peut-on en déduire pour result1 et result2 ?
  4. Vous vous trouvez sur une case quelconque, de coordonnées (i, j).

    1. Pourquoi faut-il s'intéresser à la valeur des cases à gauche, en haut et haut-gauche de cette case ?

    2. 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

      1. Sur quelle case vous trouverez-vous ensuite ?
      2. Que peut-on en déduire pour result1 et result2 ?
    3. 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

      1. Sur quelle case vous trouverez-vous ensuite ?
      2. Que peut-on en déduire pour result1 et result2 ?
    4. 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

      1. Sur quelle case vous trouverez-vous ensuite ?
      2. Que peut-on en déduire pour result1 et result2 ?
    5. 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

      1. Sur quelle case vous trouverez-vous ensuite ?
      2. Que peut-on en déduire pour result1 et result2 ?
    6. Comment faire si plusieurs de ces cases contiennent un score maximum ?

  5. Appelez l'enseignant pour qu'il vérifie vos réponses aux questions précédentes.

  6. 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ères mot1 et mot2.

    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.

  7. 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~