Cet article à un prédécesseur.
S’affranchir de ChatGPT
Lors d’un épisode précédent j’avais présenté l’implémentation en TypeScript de l’algorithme de Needleman et Wunsch pour aligner de façon optimale des séquences biologiques. Dérouté par la façon inhabituelle (pour moi) dont TypeScript et JavaScript créent, remplissent et lisent les tableaux, j’avais demandé l’aide de ChatGPT, et l’avais obtenue, mais au prix d’une simplification qui diminuait la lisibilité des résultats.
En effet, lorsque j’avais programmé cet algorithme en Scheme (ici pour le backtracking) et en Rust, le tableau des scores (des valeurs numériques) était présenté avec dans la première ligne les symboles des nucléotides (ou des acides aminés) de la première séquence, et dans la première colonne ceux de la seconde séquence, ce qui permettait de voir et de comprendre à quelle paire de nucléotides (ou d’acides aminés) correspondait quel score, et comment ils se succédaient.
ChatGPT s’était simplifié la vie en ne produisant qu’un tableau homogène, purement numérique, des scores, mais de ce fait assez peu lisible. Je voulais revenir à la présentation initiale. Pour ce faire j’ai décidé de me passer des services de ChatGPT.
Le calcul des scores
On trouvera exposés dans un autre article les principes de l’algorithme Needleman et Wunsch. Rappelons simplement ici les principes de calcul des scores.
À chaque position Mi,j de la matrice M (i est le numéro de ligne, j le numéro de colonne) le score se calcule ainsi :
Mi,j = maximum de :
– Mi-1,j-1 + Si,j (concordance ou discordance dans la diagonale) ;
– Mi,j-1 + w (gap dans la séquence n° 1) ;
– Mi-1,j + w (gap dans la séquence n° 2).
Ce que l’on peut représenter par un schéma ainsi :
Nous voyons que pour calculer Mi,j il faut (et il suffit de) connaître Mi-1,j, Mi,j-1 et Mi-1,j-1 ; de ce point de vue le problème est assez analogue à ceux posés par Fibonacci ou par le triangle de Pascal aux articles précédents.
La principale difficulté était la manipulation des indices en tenant compte du style de TypeScript et de JavaScript, qui consiste à remplir les lignes de tableau en commençant par placer la valeur de la dernière case en début de ligne, puis à la repousser vers la fin au fur et à mesure que l’on introduit les valeurs des cases précédentes, par la méthode unshift().
Le programme principal
Pour un programme bien structuré il est de bonne politique que le programme principal borne son action à l’ordonnancement des différents sous-programmes et aux interactions avec le monde extérieur. Les entrées-sorties, que ce soit dans des fichiers ou sur la ligne de commande, sont laborieuses en TypeScript/JavaScript, parce qu’à l’origine ces langages n’étaient pas destinés à cet usage, mais on y arrive quand même :
#!/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) {
const resultat = score_NW.score_NW(s1, s2, S, gap);
console.table(resultat.T);
console.log(resultat.ls1 + 2, resultat.ls2 + 2, resultat.s1, resultat.s2, resultat.S, resultat.gap);
console.table(score_NW.aligne_NW(resultat));
}La méthode de calcul des scores
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, ls2, s1, s2, S, gap };
}La méthode de retour sur trace (backtracking)
// Backtracking à partir de l'objet retourné
public aligne_NW(result: {
T: [][],
ls1: number,
ls2: number,
s1: string,
s2: string,
S: number,
gap: number
}): string[] {
const { T, ls1, ls2, s1, s2, S, gap } = result;
let i = ls1 + 1;
let j = ls2 + 1;
let iseq = ls2 - 1;
let jseq = ls1 - 1;
console.log(T[j][i], s1[jseq], s2[iseq]);
const A1: string[] = [];
const Mid: string[] = [];
const A2: string[] = [];
while (i > 1 || j > 1) {
// priorité : diag (match/mismatch), puis up (gap dans s1), puis left (gap dans s2)
if (i > 1 && j > 1) {
const mm = (s1[jseq] === s2[iseq]) ? S : 0;
if (T[j][i] === T[j - 1][i - 1] + mm) {
A1.unshift(s1[jseq]);
A2.unshift(s2[iseq]);
Mid.unshift(s1[jseq] === s2[iseq] ? "|" : "x");
i--; j--; iseq--; jseq--;
continue;
}
}
if (i > 1 && T[j][i] === T[j - 1][i] + gap) {
// gap dans s1 -> on aligne '_' sur s1
A1.unshift("_");
A2.unshift(s2[iseq]);
Mid.unshift(" ");
j--; iseq--;
continue;
}
if (j > 1 && T[j][i] === T[j][i - 1] + gap) {
// gap dans s2 -> on aligne '_' sur s2
A1.unshift(s1[jseq]);
A2.unshift("_");
Mid.unshift(" ");
i--; jseq--;
continue;
}
// En cas d'égalité flottante/incohérence, décrémentation pour éviter boucle infinie
if (i > 1 && j > 1) { i--; j--; A1.unshift(s1[jseq]); A2.unshift(s2[iseq]); Mid.unshift("?"); }
else if (i > 1) { i--; A1.unshift("_"); A2.unshift(s2[iseq]); Mid.unshift(" "); }
else if (j > 1) { j--; A1.unshift(s1[jseq]); A2.unshift("_"); Mid.unshift(" "); }
}
return [A1.join(""), Mid.join(""), A2.join("")];
}
}