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 :
- (define seq "ACCATTGCAATATAGA")
- (format "~(\\n?)" (string->list seq))
- -> A\n?C\n?C\n?A\n?T\n?T\n?G\n?C\n?A\n?A\n?T\n?A\n?T\n?A\n?G\n?A
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) :
- (module pregexp-search
- (export (pregexp-parse the-pattern in-file)))
- ;;
- (define (pregexp-parse the-pattern in-file)
- (let ((in-port (open-input-file in-file)))
- (read-line in-port) ;; sauter 1ère ligne fasta
- (analyse the-pattern (get-data in-port))
- (close-input-port in-port)))
- ;;
- (define (multiline str)
- (format "~(\\n?)" (string->list str)))
- ;;
- (define (get-data in-port)
- (read-string in-port)) ;; Pour lire TOUT le fichier dans une ligne
- ;;
- (define (put-data start pos-0 end-pos)
- (print "From " (+ start pos-0) " to " (+ start end-pos)))
- ;;
- (define (analyse pattern sequence)
- (let ((regexp (pregexp (multiline pattern) 'MULTILINE))
- (len (string-length sequence)))
- (let loop ((start 0))
- (let ((result (pregexp-match-positions regexp sequence start len)))
- (if result
- (begin
- (put-data start (caar result) (cdar result))
- (loop (+ start (cdar result)))) ) ) )))
Et le module de pilotage de l’ensemble :
- (module benchmark-screen
- (main bench)
- (import pregexp-search))
- ;;
- (define (bench Args)
- (let ((the-pattern (cadr Args))
- (in-file (caddr Args)))
- (newline)
- (print "Résultats Posix Regexp Multiline")
- (multiple-value-bind (res rtime stime utime)
- (time (lambda () (pregexp-parse the-pattern in-file)))
- (print "real: " rtime "ms sys: " stime "ms user: " utime))
- ))
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