Un de mes étudiants du Cnam, Paul Bachelerie, m’a soumis un projet qu’il souhaitait résoudre en Scheme, et dont la solution demandait quelques connaissances non abordées en cours. Le laboratoire où il accomplissait un stage lui avait demandé de le faire en Python, et il voulait comparer les deux langages.

Le projet consistait à rechercher, au moyen d’expressions régulières, des motifs dans la séquence d’un génome bactérien enregistré dans un fichier au format Fasta. C’est plus compliqué que la recherche exacte d’un mot, pour laquelle on peut utiliser l’algorithme de Knuth-Morris-Pratt, mais moins compliqué que la recherche de similitudes par optimisation d’alignement selon l’algorithme de Needleman et Wunsch.

Le format Fasta est très simple : une ligne d’en-tête décrit la séquence, dont le texte suit, en lignes de 70 caractères :

Et voici le génome complet ici :

Toute la solution consiste à s’affranchir des caractères de fin de ligne (cf. la procédure multiline, et la documentation qui l’explique) et à lire tout le fichier en mémoire (heureusement c’est un génome procaryote).

La procédure multiline invoque la procédure format, utilisée ici pour insérer après chaque caractère du motif l’expression régulière décrite ainsi : ~(\\n?), qui introduit la possibilité d’un saut de ligne à n’importe quel emplacement du motif. Ainsi :

Quant à la procédure read-string utilisée par get-data elle lit jusqu’à épuisement le flux de données ouvert par in-port et renvoie le résultat sous forme d’une chaîne de caractères.

Manuel Serrano, auteur de Bigloo, nous promet pour bientôt une version basée sur mmap, qui fera en gros la même chose mais plus efficacement.

Voilà le code (ci-dessous celui du module principal) :

Et le module de pilotage de l’ensemble :

Ce programme s’utilise ainsi :

./bin/benchmark-screen CAATATAGGCATAGCGCACA sequence_E-coli.fasta

et le résultat est ainsi :

Résultats Posix Regexp Multiline
From 138 to 159
real: 230ms sys: 100ms user: 130

Il faut une version récente du compilateur Bigloo