EduAlign

Masquer les consignes Afficher les consignes À propos

Bienvenue sur EduAlign !

Cette application pédagogique vous permet de comprendre et d'explorer pas à pas le fonctionnement de l'algorithme d'alignement de Needleman-Wunsch.

1. Choisissez vos données : Saissez les séquences que vous voulez aligner (maximum 30 caractères, seules les 26 lettres de l'alphabet sont autorisées).
2. Définissez vos paramètres : Ajustez les récompenses et les pénalités pour les identités (match), les substitutions (mismatch) et les lacunes (gap). Les paramètres par défaut (1, -1, -1) sont utilisables pour aligner des séquences d'ADN ou de protéines. Les paramètres (0, -1, -1) permettent de calculer la distance d'édition entre deux mots, elle sera égale à l'opposé du score d'alignement final. L'algorithme de Needleman-Wunsch est alors équivalent à celui de Wagner-Fischer.
3. Mode pas à pas : Activez ou désactivez l'option pour suivre chaque étape de l'alignement ou obtenir directement le résultat final.
4. Remplissage accéléré : Activez cette option pour passer le remplissage des matrices case par case, les autres phases de l'algorithme ne sont pas affectées.
5. Lancez l'alignement : Cliquez sur le bouton Aligner pour générer les matrices des scores et des traces, ainsi que les alignements finaux. Les modifications des données, des paramètres ou des options ne sont pas prises en compte une fois que l'algorithme a été lancé. Vous pouvez recliquer sur Aligner à n'importe quel moment pour redémarrer l'algorithme du début.

Suivez l'algorithme étape par étape pour mieux le comprendre. Survolez la matrice des scores pour afficher les calculs dans une infobulle. Construisez l'alignement optimal en suivant le chemin de la matrice des traces.

À vous de jouer !

Données

Séquences à aligner	Alignement optimal
PLANTE
PENTES

Paramètres

Identité (match) :	1
Substitution (mismatch) :	-1
Lacune (gap) :	-1

Actions

Les matrices et des explications détaillées apparaitront ici lorsque vous lancerez l'algorithme d'alignement.

Démarrage avec deux matrices vides : L'algorithme commence par initialiser deux matrices, la matrice des scores et la matrice des traces. La matrice des scores est utilisée pour enregistrer les scores cumulés permettant d'aligner un préfixe de la première séquence avec un préfixe de la seconde séquence. Elle représente l'ensemble des possibilités d'alignement sous forme d'un tableau bidimensionnel, où chaque cellule correspond à une étape intermédiaire d'alignement. La première séquence est associée aux lignes et la seconde séquence aux colonnes. La matrice des traces, quant à elle, est conçue pour garder en mémoire les directions d'où proviennent les scores optimaux dans la matrice des scores. Ces directions (⭦, ⭡, ⭠) sont cruciales pour reconstruire l'alignement optimal lors de la phase de backtracking. Au départ, ces deux matrices sont vides à l'exception d'un score nul inscrit dans la cellule (0, 0).

Initialisation de la première ligne : La première ligne de la matrice des scores est remplie pour représenter l'alignement d'une séquence vide avec un préfixe de la seconde séquence. Chaque cellule de cette ligne est calculée en cumulant les pénalités de lacunes, puisque seul un alignement avec des lacunes est possible dans ce cas. Ainsi, la cellule (0, j) contient le score j * gap, où gap est la pénalité définie par l'utilisateur. Dans la matrice des traces, chaque cellule de cette ligne est marquée par une direction gauche (⭠), indiquant que ces scores sont obtenus par l'ajout successif de lacunes dans la première séquence.

Initialisation de la première colonne : La première colonne de la matrice des scores est remplie pour représenter l'alignement d'un préfixe de la première séquence avec une séquence vide. Comme pour la première ligne, chaque cellule est calculée en cumulant les pénalités de lacunes, avec le score i * gap pour la cellule (i, 0). Dans la matrice des traces, chaque cellule de cette colonne est marquée par une direction haut (⭡), indiquant que les scores sont obtenus par l'ajout successif de lacunes dans la seconde séquence.

Remplissage des matrices ligne par ligne : Cette étape constitue le cœur de l'algorithme. Pour chaque cellule (i, j) de la matrice (autre que celles de la première ligne et de la première colonne), trois scores possibles sont calculés : le score pour une correspondance de position entre les deux séquences (⭦), le score pour une lacune dans la première séquence (⭠), et le score pour une lacune dans la seconde séquence (⭡). Le score maximal parmi ces trois possibilités est enregistré dans la cellule (voir l'infobulle), reflétant le meilleur alignement possible pour les préfixes correspondants des deux séquences. La matrice des traces est simultanément mise à jour pour enregistrer la provenance du score maximal (diagonale, haut, ou gauche). En cas d'égalité l'algorithme fait un choix arbitraire. Toutes les cellules de la matrice sont ainsi progressivement remplies jusqu'à atteindre le coin inférieur droit.

Retour sur trace (backtracking) : Une fois la matrice des scores complètement remplie, l'algorithme utilise la matrice des traces pour reconstruire l'alignement optimal. Le processus commence dans la cellule finale (m, n) de la matrice, où m et n représentent les longueurs des séquences 1 et 2. En suivant les directions indiquées (⭦, ⭡, ⭠), l'algorithme remonte dans la matrice jusqu'à atteindre la cellule (0, 0). Chaque direction correspond à une décision : une diagonale (⭦) aligne deux caractères, un déplacement horizontal (⭠) introduit une lacune dans la première séquence, et un déplacement vertical (⭡) introduit une lacune dans la seconde. Cette étape produit les deux séquences alignées, prêtes à être affichées.

Alignement terminé : Lorsque l'algorithme atteint la cellule (0, 0), l'alignement optimal est entièrement reconstruit. Le score global, situé dans la cellule (m, n), représente le meilleur score possible pour aligner les deux séquences en fonction des paramètres définis. L'utilisateur peut visualiser les séquences alignées, les lacunes introduites, et le chemin suivi dans la matrice pour parvenir à cette solution optimale.