La question
Je tente maintenant l’implémentation en TypeScript de l’algorithme de Needleman et Wunsch pour aligner de façon optimale des séquences biologiques. Dans un premier temps on construit un tableau de scores d’alignement, ce que j’ai fait et qui fonctionne correctement. Puis je passe le tableau résultat en argument à la méthode qui construit l’alignement par retour sur trace (backtraking). Et là j’ai un problème de gestion de tableau et de boucle while pour traiter les différents cas possibles. Voici le programme principal :
#!/usr/bin/env -S npx tsx
// ne pas oublier : $ npm install commander
// et : $ chmod a+x main.ts
import { Command } from "commander";
import * as readline from "readline"; //
import { NW } from "./Needleman-Wunsch.js";
let score_NW = new NW;
// --- Programme principal avec Commander ---
const program = new Command();
program
.name("calcul_score")
.description("Lire séquences, score et gap depuis la ligne de commande ou depuis un fichier")
.argument("<textes...>", "Séquences, score, gap")
.action((textes: string[]) => {
calcul_score(textes[0], textes[1], Number(textes[2]), Number(textes[3]))
});
program.parse(); // déclenche le parsing des arguments
function calcul_score(s1: string, s2: string, S: number, gap: number) {
console.table(score_NW.score_NW(s1, s2, S, gap)[0]);
console.table(score_NW.aligne_NW(score_NW.score_NW(s1, s2, S, gap)));
}puis la méthode d’alignement, qui s’arrête à la première paire :
export class NW {
public score_NW(s1: string, s2: string, S: number, gap: number) {
let ls1: number = s1.length;
let ls2: number = s2.length;
let T: [][] = [];
T.push([0]);
T[0].push(0);
T.push([0]);
T[1].push(0);
for (let j = 2; j < ls1 + 2; j++) {
T[0].push(s1[j - 2]);
T[1].push(gap * (j - 1));
}
for (let i = 2; i < ls2 + 2; i++) {
T[i] = [];
T[i].push(s2[i - 2]);
T[i].push(gap * (i - 1));
for (let j = 2; j < ls1 + 2; j++) {
let concorde: number = 0;
if (s1[j - 2] === s2[i - 2]) {
concorde = 1;
}
T[i].push(Math.max((T[i - 1][j - 1] + concorde),
(T[i - 1][j] + gap),
(T[i][j - 1] + gap)));
}
}
return [T, ls1+2, ls2+2];
}
public aligne_NW(T: [], gap: number): string[] {
const C: [][] = T[0];
const nlin: number = T[2];
const ncol: number = T[1];
console.log(nlin, ncol);
let Alignement: string[][] = [];
Alignement.push([]);
Alignement.push([]);
Alignement.push([]);
console.table(Alignement);
let position: number = nlin + ncol - 5;
let i: number = nlin - 1;
let j: number = ncol - 1;
do {
if (j === 0 && i > 0) {
Alignement[0].unshift("_");
Alignement[1].unshift(" ");
Alignement[2].unshift(C[i][0]);
i = i - 1;
break;
}
if (i === 0 && j > 0) {
Alignement[0].unshift(C[0][j]);
Alignement[1].unshift(" ");
Alignement[2].unshift("_");
j = j - 1;
break;
}
if (C[i][0] === C[0][j]) {
Alignement[0].unshift(C[0][j]);
Alignement[1].unshift("I");
Alignement[2].unshift(C[i][0]);
i = i - 1;
j = j - 1;
break;
}
if (C[i][j] === C[i - 1][j - 1]) {
Alignement[0].unshift(C[0][j]);
Alignement[1].unshift("x");
Alignement[2].unshift(C[i][0]);
i = i - 1;
j = j - 1;
break;
}
if (C[i][j] === C[i - 1][j] + gap) {
Alignement[0].unshift("_");
Alignement[1].unshift(" ");
Alignement[2].unshift(C[i][0]);
i = i - 1;
break;
}
if (C[i][j] === C[i][j - 1] + gap) {
Alignement[0].unshift(C[0][j]);
Alignement[1].unshift(" ");
Alignement[2].unshift("_");
j = j - 1;
break;
}
} while ( i > 0 && j > 0);
return Alignement;
}
}Bien sûr on commence par la fin et on remonte vers le début, d’où la méthode unshift(). Qu’en penses-tu ?
Analyse du problème
1. Les break
Chaque if se termine par un break, donc dès qu’un cas est rencontré, la boucle do...while s’arrête.
Or ici, il faut continuer à décrémenter i et j jusqu’à atteindre 0, sans sortir de la boucle.
➡️ Il faut remplacer les break par continue (ou mieux : réécrire en while clair).
2. Structure du tableau T
Dans score_NW(), tu construis T comme une matrice contenant à la fois des caractères (séquences) et des valeurs numériques (scores).
Cela rend l’accès complexe : C[i][0] est parfois une lettre, parfois un nombre.
➡️ Pour le backtracking, il est préférable d’avoir une matrice uniquement numérique (scores) et les séquences à part.
Puisque ta boucle et la gestion des tableaux sont correctes, le problème vient très probablement de la manière dont tu calcules les scores (et donc des tests pendant le backtracking). Je vois plusieurs points concrets qui rendent l’alignement non optimal dans ton code actuel :
– tu définis concorde = 1 pour un match et 0 sinon — donc un mismatch vaut 0, alors qu’il devrait généralement être pénalisé (ou au moins avoir un score différent du match). En pratique il faut une matrice de substitution (ici un simple +S / -S) ou au moins match = +S et mismatch = -S.
– dans score_NW() tu n’utilises pas le paramètre S que tu passes ; ça explique pourquoi le critère de match/mismatch est trop faible.
– tu mélanges lettres et nombres dans la même matrice T. Ça peut marcher mais rend les indices fragiles. Mieux : garder une matrice numérique (scores) et garder les séquences s1, s2 séparément.
– lors du backtracking, il faut comparer le score courant avec diag + score_match/mismatch, up + gap et left + gap (en testant la condition exacte : score[i][j] === score[i-1][j-1] + valeur_diag), pas seulement comparer lettres ou égalités sans tenir compte des valeurs ajoutées.
Je te propose ci-dessous une implémentation TypeScript corrigée et compacte (garde la forme proche de la tienne). Elle assume que S est le score de match et que gap est une valeur négative (par ex. S = 1, gap = -1). Le mismatch est -S (tu peux modifier si tu veux une autre table).
Code corrigé (TypeScript)
export class NW {
// Retourne un objet contenant la matrice de scores et infos utiles
public score_NW(s1: string, s2: string, S: number, gap: number) {
const n = s1.length; // colonnes
const m = s2.length; // lignes
// matrice (m+1) x (n+1) initialisée à 0
const M: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// initialisation première ligne / colonne (gap cumulé)
for (let j = 1; j <= n; j++) M[0][j] = M[0][j - 1] + gap;
for (let i = 1; i <= m; i++) M[i][0] = M[i - 1][0] + gap;
// remplissage
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const matchOrMismatch = (s1[j - 1] === s2[i - 1]) ? S : -S;
const diag = M[i - 1][j - 1] + matchOrMismatch;
const up = M[i - 1][j] + gap; // gap dans s1 (insertion dans s1)
const left = M[i][j - 1] + gap; // gap dans s2 (insertion dans s2)
M[i][j] = Math.max(diag, up, left);
}
}
return { M, n, m, s1, s2, S, gap };
}
// Backtracking à partir de l'objet retourné
public aligne_NW(result: {
M: number[][],
n: number,
m: number,
s1: string,
s2: string,
S: number,
gap: number
}): string[] {
const { M, n, m, s1, s2, S, gap } = result;
let i = m;
let j = n;
const A1: string[] = [];
const Mid: string[] = [];
const A2: string[] = [];
while (i > 0 || j > 0) {
// priorité : diag (match/mismatch), puis up (gap dans s1), puis left (gap dans s2)
if (i > 0 && j > 0) {
const mm = (s1[j - 1] === s2[i - 1]) ? S : -S;
if (M[i][j] === M[i - 1][j - 1] + mm) {
A1.unshift(s1[j - 1]);
A2.unshift(s2[i - 1]);
Mid.unshift(s1[j - 1] === s2[i - 1] ? "|" : "x");
i--; j--;
continue;
}
}
if (i > 0 && M[i][j] === M[i - 1][j] + gap) {
// gap dans s1 -> on aligne '_' sur s1
A1.unshift("_");
A2.unshift(s2[i - 1]);
Mid.unshift(" ");
i--;
continue;
}
if (j > 0 && M[i][j] === M[i][j - 1] + gap) {
// gap dans s2 -> on aligne '_' sur s2
A1.unshift(s1[j - 1]);
A2.unshift("_");
Mid.unshift(" ");
j--;
continue;
}
// Sécurité : en cas d'égalité flottante/incohérence, sortir proprement
// On force une décrémentation pour éviter boucle infinie
if (i > 0 && j > 0) { i--; j--; A1.unshift(s1[j]); A2.unshift(s2[i]); Mid.unshift("?"); }
else if (i > 0) { i--; A1.unshift("_"); A2.unshift(s2[i]); Mid.unshift(" "); }
else if (j > 0) { j--; A1.unshift(s1[j]); A2.unshift("_"); Mid.unshift(" "); }
}
return [A1.join(""), Mid.join(""), A2.join("")];
}
}Cet article a un prédécesseur.