🧬 Aligneur de séquences ADN — Smith-Waterman en direct

Smith-Waterman est un algorithme de programmation dynamique permettant de trouver l'alignement local optimal entre deux séquences. Contrairement à Needleman-Wunsch, qui aligne les séquences de bout en bout, Smith-Waterman permet à l'alignement de commencer et de s'arrêter n'importe où, ce qui le rend idéal pour trouver une courte région correspondante — comme une lecture de séquençage ou un fragment de gène — à l'intérieur d'une séquence plus longue et par ailleurs sans rapport. Il fonctionne en remplissant une matrice de score cellule par cellule à l'aide de la récurrence H(i,j) = max(0, H(i-1,j-1)+s(a,b), H(i-1,j)-lacune, H(i,j-1)-lacune), puis en retraçant depuis la cellule au score le plus élevé jusqu'à ce que le score revienne à zéro.

Chaque cellule H(i,j) représente le meilleur score d'alignement local se terminant à la position i de référence et j de lecture. Elle prend le maximum de quatre options : démarrer un tout nouvel alignement ici (score 0), étendre une correspondance ou incompatibilité diagonale depuis H(i-1,j-1), étendre une lacune dans la lecture depuis H(i-1,j), ou étendre une lacune dans la référence depuis H(i,j-1). Comme les scores sont plafonnés à zéro par le bas, toute série de mauvaises correspondances réinitialise simplement l'alignement local au lieu de rendre tout le score négatif, ce qui distingue précisément l'alignement local de l'alignement global.

Le score de correspondance récompense l'alignement de bases identiques entre elles ; la pénalité d'incompatibilité est soustraite quand deux bases différentes sont forcées de s'aligner ; la pénalité de lacune est soustraite chaque fois que l'algorithme ouvre une lacune (une insertion ou une délétion) dans l'une ou l'autre séquence. Augmenter la pénalité de lacune par rapport à la pénalité d'incompatibilité fait préférer à l'aligneur les substitutions aux indels, et vice versa — le même compromis que les véritables aligneurs ajustent lors de l'appel de variants génétiques à partir de lectures de séquençage bruitées.

Les véritables lectures de séquençage s'alignent rarement bord à bord avec une référence — elles contiennent généralement la région d'intérêt intégrée dans une séquence d'adaptateur, des erreurs de séquençage ou un contexte génomique voisin. Compléter le noyau muté d'ADN aléatoire inutile des deux côtés démontre la force clé de Smith-Waterman : il trouve et note uniquement la meilleure région locale correspondante, en ignorant complètement les flancs sans rapport, plutôt que de forcer un alignement sur toute la lecture.

Percent identity is the fraction of columns in the traced-back local alignment where the reference and read bases are identical. It is computed directly from the traceback path, not estimated, so it reflects exactly the alignment the algorithm reports as optimal for the current scoring scheme.

Oui. La récurrence de score, la règle de plafonnement à zéro, le choix de la cellule au score maximal et le retour en arrière sont tous implémentés exactement comme dans la formulation originale de Smith & Waterman (1981) avec une pénalité de lacune linéaire. Elle omet le score de lacune affine (un coût distinct d'ouverture et d'extension de lacune) et les matrices de substitution d'acides aminés, que de véritables aligneurs comme BLAST ou BWA ajoutent par-dessus cette même récurrence de base.