Comment aligner deux séquences ?
Aligner deux séquences, c’est les écrire l’une sous l’autre pour faire ressortir ce qu’elles ont en commun. On glisse parfois un trou pour que les lettres semblables se retrouvent en face.
Un score dit si l’alignement est bon. Vous allez calculer ce score, d’abord à la main, puis avec un tableau rempli par le programme.
À la fin de cette leçon
Remarque
Je peux calculer le score d’un alignement de deux séquences avec un tableau.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Alignement | deux séquences écrites l’une sous l’autre | |
| Correspondance | deux bases identiques en face l’une de l’autre | |
| Différence | deux bases différentes en face l’une de l’autre | |
| Trou | un tiret qui remplace une base manquante | - |
| Score | la somme des points de chaque colonne |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un alignement se note colonne par colonne
On fixe trois points. Une correspondance vaut +1. Une différence vaut -1. Un trou vaut -2, car en perdre une base coûte plus qu’une erreur.
Le score de l’alignement est la somme des points de toutes les colonnes.
Exemple travaillé : ACGTTA contre ACTTA
| Colonne | 1 | 2 | 3 | 4 | 5 | 6 | Score |
|---|---|---|---|---|---|---|---|
| Première séquence | A | C | G | T | T | A | |
| Seconde séquence | A | C | - | T | T | A | |
| Points | +1 | +1 | -2 | +1 | +1 | +1 | 3 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le meilleur alignement a le plus fort score
Pour deux séquences, il existe beaucoup d’alignements possibles. L’alignement global garde le meilleur, celui qui lit les deux séquences en entier.
Essayer tous les trous est trop long. On remplit donc un tableau : chaque case contient le meilleur score des débuts des deux séquences.
Calculer le score d’une paire alignée
docker exec jupyter python3 -c "a='ACGTTA'; b='AC-TTA'; print(sum(1 if x==y else -2 if '-' in (x,y) else -1 for x,y in zip(a,b)))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que la commande calcule
La commande prend la paire alignée du tableau. Pour chaque colonne, elle donne +1 si les bases sont égales, -2 s’il y a un trou et -1 sinon, puis elle additionne.
Elle affiche 3, le score du tableau précédent.
Chaque case choisit parmi trois chemins
Une case se calcule avec ses trois voisines. En venant de la diagonale, on ajoute +1 ou -1 selon que les deux bases sont égales. En venant du haut ou de la gauche, on ajoute -2 : c’est un trou.
On garde le plus grand des trois. La dernière case donne le score global.
Exemple travaillé : le tableau de ACT et AT
| début | A | T | |
|---|---|---|---|
| début | 0 | -2 | -4 |
| A | -2 | 1 | -1 |
| C | -4 | -1 | 0 |
| T | -6 | -3 | 0 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Remplir le tableau avec des boucles
def score_global(a, b):
gain = 1
erreur = -1
trou = -2
# Le tableau a une ligne de plus que a et une colonne de plus que b.
tableau = []
for i in range(len(a) + 1):
tableau.append([0] * (len(b) + 1))
for i in range(1, len(a) + 1):
tableau[i][0] = i * trou
for j in range(1, len(b) + 1):
tableau[0][j] = j * trou
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
diagonale = tableau[i - 1][j - 1] + gain
else:
diagonale = tableau[i - 1][j - 1] + erreur
haut = tableau[i - 1][j] + trou
gauche = tableau[i][j - 1] + trou
tableau[i][j] = max(diagonale, haut, gauche)
for ligne in tableau:
print(ligne)
return tableau[len(a)][len(b)]
print("score", score_global("ACT", "AT"))
Une erreur fréquente
Attention
Beaucoup pensent qu’un alignement sans trou est toujours le meilleur. Un trou coûte -2, mais deux différences coûtent aussi -2. Quand le trou remet en face plusieurs bases égales, il fait gagner des points.
Pour aller plus loin
Dans votre carnet, appelez votre fonction sur ACGTTA et ACTTCA, puis sur deux séquences de huit bases de votre invention.
Dites si le meilleur alignement utilise un trou et pourquoi.