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 :
La méthode de calcul des scores
La méthode de retour sur trace (backtracking)
Exemple
./main.ts GAATTCAGTTA GGATCGA 1 0
| (index) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 0 | ’G’ | ’A’ | ’A’ | ’T’ | ’T’ | ’C’ | ’A’ | ’G’ | ’T’ | ’T’ | ’A’ |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | ’G’ | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | ’G’ | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| 4 | ’A’ | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 |
| 5 | ’T’ | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 6 | ’C’ | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |
| 7 | ’G’ | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 5 | 5 |
| 8 | ’A’ | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 5 | 5 | 5 | 5 | 6 |
13 9 GAATTCAGTTA GGATCGA 1 0
6 A A
| 0 | G | A | A | T | T | C | A | G | T | T | A |
| 1 | x | ||||||||||
| 2 | G | G | A | _ | T | C | _ | G | _ | _ | A |