Alignement de séquences

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 à les comparer.

Chaque composant de ces macromolécules pouvant être représenté par une lettre, un alignement de séquences peut ressembler à ça :

source : https://fr.wikipedia.org/wiki/Alignement_de_séquences

Ces alignements sont réalisés par des algorithmes dont l’objectif est de maximiser le nombre de coïncidences entre les « lettres » dans les différentes séquences. Ceci nécessite en général l’introduction de « trous » (caractère "-") à certaines positions dans les séquences, de manière à aligner les caractères communs sur des colonnes successives.

Supposons que l’on souhaite aligner 2 chaînes de caractères, avec les contraintes suivantes :

• tous les caractères des 2 chaînes doivent être utilisés,
• ils doivent rester dans l’ordre,
• on ne doit jamais aligner deux « trous » (caractère "-"),
• les 2 chaînes n’ont pas obligatoirement la même longueur.

Par exemple, pour les chaines "SCIENCE" et "SILENCE", il existe de nombreuses combinaisons :

SCI-ENCE
S-ILENCE

ou

SCIENCE
SILENCE

ou

SCI-E-NCE
-SIL-ENCE

Mais parmi tous les alignements possibles on cherche celui qui aura le meilleur score, calculé ainsi :

• alignement de 2 caractères identiques : +1 point
• alignement de 2 caractères différents (y compris le caractère « -« ) : -1 point

SCI-ENCE
S-ILENCE

SCIENCE
SILENCE

SCI-E-NCE
-SIL-ENCE

Algorithme récursif

Un algorithme récursif pourrait consister à déterminer 3 scores :

• score 1 : on compare les dernières lettres des 2 chaînes :
  • soit elles sont identiques :
    • on marque 1 point
  • soit elles ne le sont pas :
    • on perd 1 point
  • on ajoute le score de l’alignement des 2 sous-chaînes diminuées de leur dernier caractère
• score 2 : on « compare » la dernière lettre de la 1^ère chaîne à « – » (caractère « trou » qui ne se trouve pas réellement dans les chaînes)
  • on perd 1 point
  • on ajoute le score de l’alignement de la 1^ère chaîne diminuée de son dernier caractère et de la 2^ème chaîne
• score 3 : on « compare » la dernière lettre de la 2^ème chaîne à « – »
  • on perd 1 point
  • on ajoute le score de l’alignement de la 2^ème chaîne diminuée de son dernier caractère et de la 1^ère chaîne
• on retourne le meilleur des 3 scores
• les appels récursifs cessent dès qu’une des chaînes est vide :
  • le score retourné vaut alors l’opposé de la taille de l’autre chaîne (celle qui n’est pas vide)

"DPGDFDRNVPRICGVCGDRATGFHFNAMTCEGCKGFFRRSMKRKALFTCPFNGDCRITKDNRRHCQLKRCVDIGMMKEFILTD"
"IRPQKRKKGPAPKMLGNELCSVCCGDKASGFHYNVLSCEGCKGFFRRSVIKGAHYICHSGGHCPMDTYMRRKCQECRLRKCRQAGMREECVLSE"

Programmation dynamique

Contrairement au problème du rendu de monnaie, la fonction aligne attend 2 arguments. Pour mettre en cache ses résultats, on doit donc utiliser une structure à 2 dimensions : un tableau, soit une liste de listes en Python.

Par exemple, pour les chaines "SCIENCE" et "SILENCE", le tableau pourrait être organisé ainsi :

Si le tableau est implémenté en Python par l’instruction suivante :

s = [[0]*(n2+1) for _ in range(n1+1)]

avec n1 et n2 les longueurs des deux chaînes passées à la fonction aligne.

chaque case s[i][j] doit contenir le meilleur score de l’alignement de s1[:i] avec s2[:j].

Reste à compléter ce tableau avec les meilleurs scores. Pour cela on peut observer comment sont obtenus les 3 scores du cas récursif de l’algorithme précédent :

On constate que le score s[i][j] peut être simplement calculé à partir des scores s[i-1][j-1], s[i][j-1] et s[i-1][j].

Dans le tableau, cela peut s’illustrer de la manière suivante :

Il faut donc remplir le tableau dans le sens des indices croissants.

L’algorithme dynamique se déroule donc en 3 grandes étapes :

1. On créé le tableau, tel que la case s[0][0] = 0
   (pas de lettres → score nul)
2. On rempli les cases des premières ligne et colonne telles que s[i][0] = -i et s[0][j]=-j
   (une chaîne vide → score = l’opposé de la taille de l’autre)
3. On parcoure le reste du tableau, dans l’ordre des indices croissants, et on calcule le score comme le maximum des 3 scores calculés précédemment :
   • score 1 : s[i-1][j-1]
     • -1 si les lettres d’indices i-1 et j-1 sont différentes
     • +1 si les lettres d’indices i-1 et j-1 sont identiques
       remarque : les indices des lettres dans les chaînes commencent à 0, ce qui explique le -1 .
   • score 2 : -1 + s[i][j-1]
   • score 3 : -1 + s[i-1][j]