Projet

Cours/Algorithmie/Design d'algorithmes/Programmation dynamique/Alignement de séquences/Projet

Prérequis :

Programmation Objet

Le but de ce projet est de coder les différents algorithmes d'alignement de séquences vus dans la partie précédente.

On considérera pour ce projet que le caractère "-" ne fait pas partie de l'alphabet $\mathcal{A}$ utilisé.

Alignement

On rappelle qu'un alignement est un couple de deux séquences $(a^\star, b^\star)$ tels que :

$a^\star$ et $b^\star$ sont de même longueur $L$
chaque caractère de $a^\star$ et $b^\star$ est dans $\mathcal{A} \cup { - }$
$(a^\star_i, b^\star_i) \neq (-,-)$ pour tout $0 \leq i < L$

Représentez graphiquement l'alignement (les 2 chaînes l'une sous l'autre avec les |, comme dans l'étude)
pour un alignement $(a^\star, b^\star)$ donné, rendez les listes de chaînes de caractères permettant de passer de $a$ à $b$, comme fait dans l'étude

Pour cela :

Vous créerez une classe Alignement telle que :

le constructeur prend les deux chaînes $a^\star$ et $b^\star$
cette classe doit contenir les méthodes suivantes :
- a() qui rend $a$
- b() qui rend $b$
- affiche() qui affiche l'alignement

Par exemple, on doit être capable d'exécuter le cod suivant :

from alignement import Alignement

un_alignement = Alignement("MER-OUS", "MARLOU-")
print(un_alignement.a())  # qui doit afficher "MEROUS"
print(un_alignement.b())  # qui doit afficher "MARLOU"

un_alignement.affiche() # aui doit afficher les 3 lignes suivantes
# MER-OUS
# | | || 
# MARLOU-

Distance élémentaire

Pour deux séquences $a$ et $b$ il faut maintenant pouvoir calculer la distance d'édition avec la distance élémentaire :

calculer la matrice d'édition
rendre la distance d'édition
rendre un alignement

Pour cela :

Vous créerez une classe DistanceElem telle que :

le constructeur prend les deux chaînes $a$ et $b$
cette classe doit contenir les méthodes suivantes :
- matrice() qui rend la matrice d'édition en utilisant la distance élémentaire
- dist() qui rend la distance d'édition associée à la matrice
- alignement() qui rend un alignement associé à la matrice.

Vous vérifierez bien que les 3 alignements suivants sont corrects :

"ACTGATT" et "GCTAATCG"
"ACTGATT" et "-"
"-" et "GCTAATCG"

Evolution

On veut visualiser l'évolution permettant d'aller de $a^\star$ à $b^\star$ :

Dans la classe Alignement ajoutez une méthode evolution() qui rend la liste de chaînes permettant de passer de $a$ à $b$ en suivant l'alignement $(a^\star, b^\star)$

Le code python suivant doit pouvoir s'exécuter :

from alignement import Alignement

un_alignement = Alignement("MER-OUS", "MARLOU-")
un_alignement.evolution() # qui doit afficher les lignes suivantes

# MEROUS
# ^
# MAROUS
#  ^
# MAROUS
#   ^
# MARLOUS
#    ^
# MARLOUS
#     ^
# MARLOUS
#      ^
# MARLOU
#       ^

Cas général

On suppose que le coût est défini par une fonction dont la signature est coût(x, y=None) :

si on renseigne deux caractères x et y la fonction rend le coût de substitution entre x et y
si on ne donne qu'un paramètre, la fonction rend le coût d'insertion/suppression du caractère x

Définissez la fonction de coût pour l'exemple du cas général de l'étude

On peut maintenant créer l'alignement général :

En héritant de la classe DistanceElem, créez la classe Distance qui réalise un alignement.

le constructeur prend les deux chaînes $a$ et $b$ et la fonction de coût
cette classe doit contenir les même méthodes que la classe DistanceElem.

Arrangez-vous pour conserver le plus de code possible entre les deux classes.

Pour aller plus loin : étude biologique

Le fichier texte pro-opsines.edi contient le code (sous la formes d'acides aminées) de 3 protéines d'opsines qui permettent aux humains de voir en couleur. Ces 3 protéines dérivent d'un ancêtre commun.

Récupérez sous la forme de 3 chaînes de caractères les 3 protéines (les lignes commençant par un ";" sont considérées comme des commentaires pour ce type de fichier)
faites l'alignement élémentaire des 3 protéines 2 à 2

La distance élémentaire n'est pas très utilisée en pratique. Pour l'étude de séquences protéiques, on utilise souvent la matrice de similarité BLOSUM62 :

PROTEINS = ["A", "R", "N", "D", "C", "Q", "E", "G", "H", "I", "L", "K", "M", "F", "P", "S", "T", "W", "Y", "V", "B", "Z", "X"]

BLOSUM_MATRIX = [
  [4, -1, -2, -2, 0, -1, -1, 0, -2, -1, -1, -1, -1, -2, -1, 1, 0, -3, -2, 0, -2, -1, 0],
  [-1, 5, 0, -2, -3, 1, 0, -2, 0, -3, -2, 2, -1, -3, -2, -1, -1, -3, -2, -3, -1, 0, -1],
  [-2, 0, 6, 1, -3, 0, 0, 0, 1, -3, -3, 0, -2, -3, -2, 1, 0, -4, -2, -3, 3, 0, -1],
  [-2, -2, 1, 6, -3, 0, 2, -1, -1, -3, -4, -1, -3, -3, -1, 0, -1, -4, -3, -3, 4, 1, -1],
  [0, -3, -3, -3, 9, -3, -4, -3, -3, -1, -1, -3, -1, -2, -3, -1, -1, -2, -2, -1, -3, -3, -2],
  [-1, 1, 0, 0, -3, 5, 2, -2, 0, -3, -2, 1, 0, -3, -1, 0, -1, -2, -1, -2, 0, 3, -1],
  [-1, 0, 0, 2, -4, 2, 5, -2, 0, -3, -3, 1, -2, -3, -1, 0, -1, -3, -2, -2, 1, 4, -1],
  [0, -2, 0, -1, -3, -2, -2, 6, -2, -4, -4, -2, -3, -3, -2, 0, -2, -2, -3, -3, -1, -2, -1],
  [-2, 0, 1, -1, -3, 0, 0, -2, 8, -3, -3, -1, -2, -1, -2, -1, -2, -2, 2, -3, 0, 0, -1],
  [-1, -3, -3, -3, -1, -3, -3, -4, -3, 4, 2, -3, 1, 0, -3, -2, -1, -3, -1, 3, -3, -3, -1],
  [-1, -2, -3, -4, -1, -2, -3, -4, -3, 2, 4, -2, 2, 0, -3, -2, -1, -2, -1, 1, -4, -3, -1],
  [-1, 2, 0, -1, -3, 1, 1, -2, -1, -3, -2, 5, -1, -3, -1, 0, -1, -3, -2, -2, 0, 1, -1],
  [-1, -1, -2, -3, -1, 0, -2, -3, -2, 1, 2, -1, 5, 0, -2, -1, -1, -1, -1, 1, -3, -1, -1],
  [-2, -3, -3, -3, -2, -3, -3, -3, -1, 0, 0, -3, 0, 6, -4, -2, -2, 1, 3, -1, -3, -3, -1],
  [-1, -2, -2, -1, -3, -1, -1, -2, -2, -3, -3, -1, -2, -4, 7, -1, -1, -4, -3, -2, -2, -1, -2],
  [1, -1, 1, 0, -1, 0, 0, 0, -1, -2, -2, 0, -1, -2, -1, 4, 1, -3, -2, -2, 0, 0, 0],
  [0, -1, 0, -1, -1, -1, -1, -2, -2, -1, -1, -1, -1, -2, -1, 1, 5, -2, -2, 0, -1, -1, 0],
  [-3, -3, -4, -4, -2, -2, -3, -2, -2, -3, -2, -3, -1, 1, -4, -3, -2, 11, 2, -3, -4, -3, -2],
  [-2, -2, -2, -3, -2, -1, -2, -3, 2, -1, -1, -2, -1, 3, -3, -2, -2, 2, 7, -1, -3, -2, -1],
  [0, -3, -3, -3, -1, -2, -2, -3, -3, 3, 1, -2, 1, -1, -2, -2, 0, -3, -1, 4, -3, -2, -1],
  [-2, -1, 3, 4, -3, 0, 1, -1, 0, -3, -4, 0, -3, -3, -2, 0, -1, -4, -3, -3, 4, 1, -1],
  [-1, 0, 0, 1, -3, 3, 4, -2, 0, -3, -3, 1, -1, -3, -1, 0, -1, -3, -2, -2, 1, 4, -1],
  [0, -1, -1, -1, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -2, 0, 0, -2, -1, -1, -1, -1, -1]
]

pour la transformer en matrice de coût, il faut prendre l'opposé de sa valeur !
l'identité n'est plus de coût nul.

Faites un alignement 2 à 2 de ces 3 protéines en utilisant la matrice de coût associée.

Vous pourrez utiliser un dictionnaire pour créer la distance entre deux acides aminés.