Pourquoi le score change-t-il l’alignement ?
Le meilleur alignement de deux séquences dépend des points que l’on choisit. Si un trou coûte peu, on en met beaucoup. S’il coûte cher, on préfère accepter des différences.
Vous allez changer les points, comparer l’alignement global à l’alignement local et choisir le réglage qui convient à la question posée.
À la fin de cette leçon
Remarque
Je peux changer le score et le prix d’un trou et dire comment l’alignement change.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Pénalité de trou | les points retirés pour un trou | -2 |
| Alignement global | un alignement des deux séquences en entier | |
| Alignement local | l’alignement du meilleur morceau commun | |
| Réglage | le choix des trois valeurs : gain, erreur et trou | |
| Segment | un morceau continu d’une séquence |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un trou cher se met moins souvent
Gardons la paire ACGTTA et AC-TTA : cinq colonnes sont en correspondance et une est un trou. Le score est donc 5 moins le prix du trou.
Si le trou coûte -1, le score monte à 4. À -2, il vaut 3. À -4, il tombe à 1.
Exemple travaillé : un même alignement, trois prix
| Prix du trou | Correspondances | Trou | Score |
|---|---|---|---|
| -1 | +5 | -1 | 4 |
| -2 | +5 | -2 | 3 |
| -4 | +5 | -4 | 1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Comparer trois prix de trou
docker exec jupyter python3 -c "a='ACGTTA'; b='AC-TTA'; print([sum(1 if x==y else gap if '-' in (x,y) else -1 for x,y in zip(a,b)) for gap in (-1,-2,-4)])"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.
L’alignement local cherche le meilleur morceau commun
Le global lit les deux séquences en entier. Deux séquences qui ne se ressemblent que sur un morceau y perdent des points sur les bords.
L’alignement local garde seulement le meilleur segment commun. Dans le tableau, une case qui deviendrait négative est remise à zéro, et le score est la plus grande case.
Exemple travaillé : global contre local
| Séquences | Global | Local | Ce que le local garde |
|---|---|---|---|
| TTTACGTACGTTT et GGACGTACGGG | -1 | 7 | le segment ACGTACG |
| ACGT et ACGT | 4 | 4 | tout, car tout correspond |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Comparer le global et le local
def meilleur_score(a, b, gain, erreur, trou, local):
tableau = []
for i in range(len(a) + 1):
tableau.append([0] * (len(b) + 1))
for i in range(len(a) + 1):
for j in range(len(b) + 1):
if i == 0 or j == 0:
if not local:
tableau[i][j] = (i + j) * trou
else:
points = erreur
if a[i - 1] == b[j - 1]:
points = gain
case = max(tableau[i - 1][j - 1] + points, tableau[i - 1][j] + trou, tableau[i][j - 1] + trou)
if local and case < 0: # en local, on repart de zéro
case = 0
tableau[i][j] = case
if not local:
return tableau[len(a)][len(b)]
meilleur = 0
for ligne in tableau:
meilleur = max(meilleur, max(ligne))
return meilleur
a = "TTTACGTACGTTT"
b = "GGACGTACGGG"
print("global", meilleur_score(a, b, 1, -1, -2, False))
print("local", meilleur_score(a, b, 1, -1, -2, True))
# Changez le prix du trou, -2, puis relancez.
Une erreur fréquente
Attention
Beaucoup croient que le local est toujours meilleur parce que son score est plus haut. Les deux scores ne répondent pas à la même question. Choisissez le global pour deux séquences du même genre, le local pour chercher un morceau commun.
Pour aller plus loin
Dans votre carnet, relancez la comparaison avec un trou à -1, puis à -6. Notez les deux scores, global et local.
Dites lequel des deux change le plus quand le trou devient cher, et pourquoi.