Le problème de l’alignement de séquences
Nature du problème
En génétique un problème récurent est celui de l’alignement de séquences.
Une séquence est une succession ordonnée d’éléments moléculaires élémentaires au sein d’une macro-molécule.
Par exemple, une molécule d’ADN est une macro-molécules constituée d’une succession ordonnée de nucléotides que l’on désigne par les lettres A, C, G et T (Ces lettres correspondent aux initiales des molécules appelées bases azotées – Adénine, Cytosine, Guanine et Thymine – qui sont présentes dans les nucléotides.)
Ainsi une séquence d’une molécule d’ADN s’écrit sous la forme d’une chaîne de caractères, comme ceci :
… ATGGCCGAGGTGTTGCGGACGCTGGCCGGAAAACCAAAATGCCACGCACTTCGACCTATGATCCTTTTCCTAATAATGCTTGTCTTGGTCTTGTTTGGTTACGGGGTCCTAAGCCCCAGAAGTCTAATGCCAGGAAGCCTGGAACGGGGGTTCTGCATGGCTGTTAGGGAACCTGACCATCTGCAGCGCGTCTCGTTGCCAAGGATGGTCTACCCCCAGCCAAAGGTGCTGACACCGTGTAGGAAGGATGTCCTCGTGGTGACCCCTTGGCTGGCTCCCATTGTCTGGGAGGGCACATTCAACATCGACATCCTCAACGAGCAGTTCAGGCTCCAGAACACCACCATTGGGTTAACTGTGTTTGCCATCAAGAAATACGTGGCTTTCCTGAAGCTGTTCCTGGAGACGGCGGAGAAGCACTTCATGGTGGGCCACCGTGTCCACTACTATGTCTTCACCGACCAGCCGGCCGCGGTGCCCCGCGTGACGCTGGGGACCGGTCGGCAGCTGTCAGTGCTGGAGGTGCGCGCCTACAAGCGCTGGCAGGACGTGTCCATGCGCCGCATGGAGATGATCAGTGACTTCTGCGAGCGGCGCTTCCTCAGCGAGGTGGATTACCTGGTGTGCGTGGACGTGGACATGGAGTTCCGCGACCACGTGGGCGTGGAGATCCTGACTCCGCTGTTCGGCACCCTGCACCCCGGCTTCTACGGAAGCAGCCGGGAGGCCTTCACCTACGAGCGCCGGCCCCAGTCCCAGGCCTACATCCCCAAGGACGAGGGCGATTTCTACTACCTGGGGGGGTTCTTCGGGGGGTCGGTGCAAGAGGTGCAGCGGCTCACCAGGGCCTGCCACCAGGCCATGATGGTCGACCAGGCCAACGGCATCGAGGCCGTGTGGCACGACGAGAGCCACCTGAACAAGTACCTGCTGCGCCACAAACCCACCAAGGTGCTCTCCCCCGAGTACTTGTGGGACCAGCAGCTGCTGGGCTGGCCCGCCGTCCTGAGGAAGCTGAGGTTCACTGCGGTGCCCAAGAACCACCAGGCGGTCCGGAACCCGTGA …
La séquence ci-dessus est celle du gène dont l’expression est à l’origine de l’appartenance d’une personne au groupe sanguin ‘A’.
La séquence ci-dessous est celle du gène dont l’expression est à l’origine de l’appartenance d’une personne au groupe sanguin ‘O’.
… ATGGCCGAGGTGTTGCGGACGCTGGCCGGAAAACCAAAATGCCACGCACTTCGACCTATGATCCTTTTCCTAATAATGCTTGTCTTGGTCTTGTTTGGTTACGGGGTCCTAAGCCCCAGAAGTCTAATGCCAGGAAGCCTGGAACGGGGGTTCTGCATGGCTGTTAGGGAACCTGACCATCTGCAGCGCGTCTCGTTGCCAAGGATGGTCTACCCCCAGCCAAAGGTGCTGACACCGTGTAGGAAGGATGTCCTCGTGGTACCCCTTGGCTGGCTCCCATTGTCTGGGAGGGCACATTCAACATCGACATCCTCAACGAGCAGTTCAGGCTCCAGAACACCACCATTGGGTTAACTGTGTTTGCCATCAAGAAATACGTGGCTTTCCTGAAGCTGTTCCTGGAGACGGCGGAGAAGCACTTCATGGTGGGCCACCGTGTCCACTACTATGTCTTCACCGACCAGCCGGCCGCGGTGCCCCGCGTGACGCTGGGGACCGGTCGGCAGCTGTCAGTGCTGGAGGTGCGCGCCTACAAGCGCTGGCAGGACGTGTCCATGCGCCGCATGGAGATGATCAGTGACTTCTGCGAGCGGCGCTTCCTCAGCGAGGTGGATTACCTGGTGTGCGTGGACGTGGACATGGAGTTCCGCGACCACGTGGGCGTGGAGATCCTGACTCCGCTGTTCGGCACCCTGCACCCCGGCTTCTACGGAAGCAGCCGGGAGGCCTTCACCTACGAGCGCCGGCCCCAGTCCCAGGCCTACATCCCCAAGGACGAGGGCGATTTCTACTACCTGGGGGGGTTCTTCGGGGGGTCGGTGCAAGAGGTGCAGCGGCTCACCAGGGCCTGCCACCAGGCCATGATGGTCGACCAGGCCAACGGCATCGAGGCCGTGTGGCACGACGAGAGCCACCTGAACAAGTACCTGCTGCGCCACAAACCCACCAAGGTGCTCTCCCCCGAGTACTTGTGGGACCAGCAGCTGCTGGGCTGGCCCGCCGTCCTGAGGAAGCTGAGGTTCACTGCGGTGCCCAAGAACCACCAGGCGGTCCGGAACCCGTGA …
Téléchargement d’un fichier : séquences ci-dessus au format txt (encodage UTF-8)
Aligner deux séquences consiste à mettre en correspondance le plus possible de « caractères » entre une séquence considérée comme étant celle de référence et l’autre séquence considérée comme la séquence dérivée de la première, d’un point de vue évolutif, en s’autorisant à introduire des ‘trous’ dans l’une ou l’autre des séquences.
Par exemple :
Avant alignement
| Séquence de référence | … ATTCGGTTACG … |
| Séquence dérivée | … ATCGGATTCG … |
Après alignement
| Séquence de référence | … ATTCGG_TTACG … |
| Séquence dérivée | … AT_CGGATT_CG … |
On pourrait envisager d’autres alignements possibles, comme celui-ci :
| Séquence de référence | … ATTCGGTTA__CG … |
| Séquence dérivée | … A_TCGG__ATTCG … |
Toutefois deux opérations sont interdites :
- la première est de retirer un caractère de l’une des deux chaînes
- et la seconde est d’aligner deux « trous » (c’est à dire deux caractères ‘_’).
L’alignement qui sera ‘choisi’ est celui qui donnera le meilleur ‘score’.
Le ‘score’ est calculé de la manière suivante :
- l’alignement de deux caractères identiques donne 1 point ;
- l’alignement de deux caractères différents enlève 1 point ;
- l’alignement d’un caractère avec un « trou » (‘_’) enlève 1 point.
Par exemple, le score de cet alignement :
| Séquence 1 | … ATTCGGTTACG … |
| Séquence 2 | … ATCGGATTCG … |
est de +5 – 5 = 0.
Le score de celui-ci :
| Séquence 1 | … ATTCGG_TTACG … |
| Séquence 2 | … AT_CGGATT_CG … |
est de +9 – 3 = +6.
Et le score de celui-ci :
| Séquence 1 | … ATTCGGTTA__CG … |
| Séquence 2 | … A_TCGG__ATTCG … |
est de +8 – 5 = +3.
C’est donc le deuxième alignement qui sera retenu.
Calculer le score de l’alignement qui suit, puis chercher un alignement qui donne un meilleur score.
| Séquence 1 | … CAAGTTCGAAC … |
| Séquence 2 | … ACAAGTCAACT … |
Analyse du problème et recherche d’une solution algorithmique
Pour résoudre le problème de l’alignement de séquences on peut chercher une solution récursive.
Considérons les deux séquences suivantes que l’on veut aligner :
| Séquence 1 | … CAGT … |
| Séquence 2 | … CGCT … |
L ‘algorithme va explorer les possibilités en partant du dernier caractère des deux séquences.
Trois cas sont alors possibles :
- conserver l’alignement des deux T , et l’algorithme va poursuivre en explorant les possibilités d’alignements de CAG avec CGC ;
- ou bien aligner le T de la séquence 1 avec un ‘trou’ ( _ ), et l’algorithme va poursuivre en explorant les possibilités d’alignements de CAG avec CGCT ;
- ou bien aligner le T de la séquence 2 avec un ‘trou’ ( _ ) et l’algorithme va poursuivre en explorant les possibilités d’alignements de CAGT avec CGC.
A chaque appel récursif la longueur de l’une ou l’autre des deux séquences ou la longueur des deux séquences diminue d’une unité.
Les appels récursifs cesseront quand la longueur de l’une des deux séquences sera égale à zéro (les caractères restant de l’autre séquence seront alors forcément alignés avec des ‘trous’).
Mais revenons sur les deux derniers évoqués plus haut.
- Cas où le T de la séquence 1 est aligné avec un ‘trou’ ( _ ), et l’algorithme poursuit alors en explorant les possibilités d’alignements de CAG avec CGCT .
Là encore 3 possibilités :- poursuivre en conservant l’alignement G/T et explorer l’alignement CA/CGC
- ou bien aligner le G avec un ‘trou’ et poursuivre en explorant l’alignement CA/CGCT
- ou bien aligner le T avec un ‘trou’ et poursuivre en explorant l’alignement CAG/CGC.
Or ce cas déjà été traité (dans le premier cas) !
- Même chose dans le cas où le T de la séquence 2 est aligné avec un ‘trou’ ( _ ) et l’algorithme poursuit alors en explorant les possibilités d’alignements de CAGT avec CGC.
Là encore 3 possibilités :- poursuivre en conservant l’alignement T/C et explorer l’alignement CAG/CG
- ou bien aligner le C avec un ‘trou’ et poursuivre en explorant l’alignement CAGT/CG
- ou bien aligner le T avec un ‘trou’ et poursuivre en explorant l’alignement CAG/CGC.
Là aussi on constate que le score de cet alignement a déjà été calculé !
Il y a donc redondance des calculs.
Ce qui rend cet algorithme peu efficace voire inefficace dès que la longueur des séquences à aligner est importante.
Il est possible aussi d’envisager un algorithme itératif.
Dans ce cas le score des alignements possibles est établi en partant du premier caractère des séquences à comparer.
| Séquence 1 | … CAGT … |
| Séquence 2 | … CGCT … |
Comme pour l’algorithme précédent on envisage trois cas :
- conserver l’alignement des deux premiers caractères C/C et continuer l’exploration des alignements possibles avec les séquences AGT/GCT
- aligner le C de la séquence 1 avec un « trou » : C/_ et continuer l’exploration des alignements possibles avec les séquences AGT/CGCT
- aligner le C de la séquence 2 avec un « trou » : _/C et continuer l’exploration des alignements possibles avec les séquences CAGT/GCT
Montrer que cet algorithme conduit aussi à une redondance de calculs.
Algorithme avec méthode dynamique
Il est possible d’améliorer les deux solutions algorithmiques qui viennent d’être présentées avec la méthode dynamique.
Les calculs de score d’alignements vont être conservés dans une structure de données au fur et à mesure qu’ils sont effectués.
Et avant de lancer le calcul du score d’un alignement donné, il s’agira de consulter cette structure de données afin de voir si un résultat n’y figure pas déjà.
Appliquons cette démarche au deuxième algorithme (celui qui explore les alignements possibles en partant du premier caractère).
Les calculs seront stockés dans une table : un tableau indexé de tableaux indexés, une liste de listes en Python.
Cette table comportera autant d’éléments que le nombre de caractères de la séquence 1 plus un.
Chaque élément sera un tableau qui comportera autant d’éléments que la longueur de la séquence 2 plus un.
Pour les séquences suivantes :
| Séquence 1 | … CAGT … |
| Séquence 2 | … CGCT … |
cette table sera la suivante :
Écrire en Python l’instruction qui permet de construire cette table.
L’implémentation en Python ne concerne que la partie de la table pour laquelle le fond des cellules est jaune pâle.
Toutes les cellules seront initialisées avec la valeur ‘zéro’ (0).
Imprimer le code et conserver le dans votre classeur.
Réponse possible et auto-évaluation de la réponse personnelle
La valeur de table[0,0] est 0, ce qui correspond au score de l’alignement de deux séquences ‘vides’.
Déterminons maintenant les autres valeurs de la première ligne : table[0, 1 ≤ 𝒿≤ 4] et de la première colonne : table[1 ≤ 𝒾≤ 4, 0] :
• table[0,1] doit contenir le score de l’alignement d’un ‘trou’ avec le caractère ‘C’ de la séquence 2.
Ce score est donc de -1.
• table[0,2] doit contenir le score de l’alignement de deux ‘trous’ avec les caractères ‘CG’ de la séquence 2.
Ce score est donc de -2
• et ainsi de suite soit le score de -3 pour table[0,3] et -4 pour table[0,4].
On remarque donc que le score est la valeur négative de l’index 𝒿.
Même chose pour la première colonne : le score est la valeur négative de l’index 𝒾.
Écrire en Python les instructions qui permettent d’initialiser les valeurs de la première ligne et de la première colonne de la table.
Imprimer le code et conserver le dans votre classeur.
Réponse possible et auto-évaluation de la réponse personnelle
Et pour les autres cellules ?
Pour calculer le score de table[𝒾,𝒿] (avec 1 ≤ 𝒾 ≤4 et 1 ≤ 𝒿≤4) on étudie les trois cas mentionnés plus haut :
• 1 – on conserve l’alignement des caractères sequence1[𝒾] et sequence2[𝒿] :
◦ Si ces deux caractères sont identiques cela ajoute 1 point (+1) au score déjà calculé pour les alignements précédents et enregistré dans table[𝒾-1, 𝒿-1] ;
◦ si ces deux caractères sont différents cela retire 1 point (-1) au score déjà calculé pour les alignements précédents et enregistré dans table[𝒾-1, 𝒿-1] ;
• 2 – on aligne le caractère sequence1[𝒾] avec un ‘trou’ ( _ ). Cela retire 1 point (-1) au score déjà calculé pour les alignement précédents et enregistré dans table[𝒾-1, 𝒿] ;
• 3 – on aligne le caractère sequence2[𝒿] avec un ‘trou’ ( _ ). Cela retire 1 point (-1) au score déjà calculé pour les alignement précédents et enregistré dans table[𝒾, 𝒿-1].
• On enregistre alors dans table[𝒾, 𝒿] le meilleur de ces trois scores.
Par exemple pour calculer le score de table[1,1] :
• on conserve l’alignement des caractères sequence1[1] = ‘C’ et sequence2[1] = ‘C’ ; comme ces deux caractères sont identiques cela ajoute 1 point (+1) au score déjà calculé pour les alignements précédents et enregistré dans table[0, 0] soit 0 + 1 = +1 ;
• on aligne le caractère sequence1[1] = ‘C’ avec un ‘trou’ (= _). Cela retire 1 point (-1) au score déjà calculé pour les alignement précédents et enregistré dans table[0, 1], soit -1 -1 = -2 ;
• on aligne le caractère sequence2[1] = ‘C’ avec un ‘trou’ (= _). Cela retire 1 point (-1) au score déjà calculé pour les alignement précédents et enregistré dans table[1, 0], soit -1 -1 = -2 ;
• On enregistre alors dans table[1,1] le meilleur de ces trois scores, à savoir +1.
Maintenant que l’on a enregistré ce score il est possible de calculer le score de table[1,2] et celui de table[2,1].
En appliquant les règles de calculs présentées plus haut, compléter ‘manuellement’ la table en calculant les autres scores.
Télécharger la ‘Fiche-Réponse‘.
Imprimer la ‘Fiche-Réponse‘ et conserver la dans votre classeur.
Réponse possible et auto-évaluation de la réponse personnelle
Si L1 est la longueur de la séquence 1 et L2 la longueur de la séquence 2, le score du meilleur alignement possible des deux séquences se trouve dans la cellule ‘table[L1,L2]’.
Implémenter en Python le programme permettant de calculer ces scores quelque soient les séquences à aligner.
Le programme sera testé avec les séquences prises en exemple.
Pour parcourir les cellules allant de table[1,1] à table[L1,L2] construire deux boucles emboîtées : la première pour 1 ≤ i ≤ L1 et la seconde pour 1 ≤ j ≤ L2.
Utiliser la fonction max() pour déterminer le meilleur des trois scores.
Imprimer le code et conserver le dans votre classeur.
Réponse possible et auto-évaluation de la réponse personnelle
Algorithme avec méthode dynamique et solution
L’alignement des deux séquences suivantes :
Séquence 1 : CAGT
Séquence 2 : CGCT
donne un score de : +2 -2 = 0
Les calculs du score du meilleur alignement montrent qu’il existe un alignement donnant un meilleur score : +1.
Mais le programme n’indique pas quel est cet alignement.
Pour palier à ce problème il est possible d’ajouter à ce programme une deuxième table dans laquelle seront stockés les alignements correspondant à chacun des meilleurs scores calculé.
Comme pour la table précédente, si L1 est la longueur de la séquence 1 et L2 la longueur de la séquence 2, cette table comportera L1 +1 lignes, et L2 +1 colonnes, soit (L1 +1) × (L2 + 1) cellules (ou ‘cases’).
Chaque cellule de cette table contiendra un n-uplet (ou tuple en Python) à deux valeurs ( = un doublet), chaque valeur étant une chaîne de caractères. Lors de la construction de cette table, ces chaînes seront vides.
Écrire en Python l’instruction qui permet de construire cette table.
Imprimer le code et conserver le dans votre classeur.
Le programme doit maintenant compléter ces deux tables.
Commençons par la première ligne et la première colonne de la table des solutions.
Pour les deux séquences suivantes :
Séquence 1 : CAGT
Séquence 2 : CGCT
voici le résultat attendu :
Imprimer le code et conserver le dans votre classeur.
Pour compléter le reste des deux tables – celle des scores et celles des solutions – l’utilisation de la fonction ‘max()’ n’est plus possible.
Il faut donc envisager une série de tests (blocs d’instructions conditionnelles).
L’algorithme complet est le suivant :
Algorithme d’alignement de séquences : début
seq1 ← séquence n°1 ; type ‘str’, non vide
seq2 ← séquence n°2 ; type ‘str’, non vide
n1 ← nombre de caractères de seq1 ; type ‘int’, différent de 0
n1 ← nombre de caractères de seq2 ; type ‘int’, différent de 0
score ← table des scores ; type ‘list’ de n1 + 1 éléments (lignes) ;
score[ligne] ← type ‘list’ de n2 +1 éléments (colonnes)
pour chaque ligne de score et chaque colonne de score[ligne]
score[ligne][colonne] ← 0
solution ← table des solutions ; type ‘list’ de n1 + 1 éléments (lignes) ;
solution[ligne] ← type ‘list’ de n2 +1 éléments (colonnes)
pour chaque ligne de solution et chaque colonne de solution[ligne]
solution[ligne][colonne] ← (‘’,’’)
pour compteur allant de 1 à n2 :
score[0][compteur] ← -compteur
sol_seq1 ← ‘_’ * compteur
sol_seq2 ← caractères de seq2 allant de 0 à compteur
solution[0][compteur] ← ( sol_seq1 , sol_seq2)
pour compteur allant de 1 à n1 :
score[compteur][0] ← -compteur
sol_seq1 ← caractères de seq1 allant de 0 à compteur
sol_seq2 ← ‘_’ * compteur
solution[compteur][0] ← ( sol_seq1 , sol_seq2)
pour ligne allant de 1 à n1
pour colonne allant de 1 à n2
score_max ← -1 + score[ligne – 1][colonne]
sol_seq1 , sol_seq2 ← solution[ligne – 1][colonne]
sol_seq1 ← sol_seq1 + seq1[ligne – 1]
sol-seq2 ← sol_seq2 + "_"
si score_max inférieur à -1 + score[ligne][colonne - 1]
score_max ← -1 + score[ligne][colonne - 1]
sol_seq1 , sol_seq2 ← solution[ligne][colonne -1]
sol_seq1 ← sol_seq1 + "_"
sol_seq2 ← sol_seq2 + seq2[colonne - 1]
si seq1[ligne - 1] identique à seq2[colonne - 1]
et score_max inférieur à 1 + score[ligne - 1][colonne – 1]
score_max ← 1 + score[ligne - 1][colonne - 1]
sol_seq1 , sol_seq2 ← solution[ligne - 1][colonne - 1]
sol_seq1 ← sol_seq1 + seq1[ligne - 1]
sol_seq2 ← sol_seq2 + seq2[colonne - 1])
si seq1[ligne - 1] différent de seq2[colonne – 1]
et score_max inférieur à -1 + score[ligne - 1][colonne - 1] :
score_max = -1 + score[ligne - 1][colonne - 1]
sol_seq1 , sol_seq2 ← solution[ligne - 1][colonne - 1]
sol_seq1 ← sol_seq1 + seq1[ligne – 1]
sol_seq2 ← sol_seq2 + seq2[colonne - 1])
score[ligne][colonne] = score_max
solution[ligne][colonne] ← (sol_seq1, sol_seq2)
renvoyer score[n1][n2],solution[n1][n2]
Fin AlgorithmeImprimer le code et conserver le dans votre classeur.
<< Cliquez pour plus d’informations <<