Un exemple intéressant de codage de l’information est la représentation des signes de l’écriture, caractères alphabétiques, sinogrammes, hiéroglyphes, chiffres, etc., désignés par le terme générique caractère.

Aux débuts du traitement des textes par ordinateur existaient deux codes rivaux : ASCII (American Standard Code for Information Interchange) et EBCDIC (Extended Binary Coded Decimal Interchange Code). Le code ASCII utilisait 7 bits, EBCDIC 8 bits, ils ne permettaient de représenter que les caractères de l’alphabet latin (sans accents, cédilles, trémas ni autres umlauts), les chiffres, les signes de ponctuation et quelques autres symboles. Ainsi, le chiffre 1 était codé 0110001 en ASCII et 11110001 en EBCDIC, pour la lettre A on avait respectivement 1000001 et 11000001, etc.

Depuis 1991 existe une norme internationale, Unicode, constituée d’un répertoire de 137 929 caractères, qui permet de désigner chaque caractère de toutes les écritures passées et présentes [1] par un nom et un code numérique, nommé point de code (codepoint).

Il existe plusieurs normes de codage informatique pour représenter les caractères Unicode, la plus répandue est UTF-8. Il est bon de savoir que les codes UTF-8 sont de taille variable, ils comportent au minimum 8 bits (d’où le nom de la norme), mais peuvent en compter jusqu’à 32 [2]. Ainsi :

Nom Unicode du caractère Point de code UTF-8 (décimal) UTF-8 (hexadécimal)
Right single quotation mark ’ U+2019 226 128 153 e28099
Apostrophe ’ U+0027 39 27
Latin small letter m U+006D 109 6d
Latin capital letter E with grave È U+00C8 195 136 c388

Le caractère Right single quotation mark est utilisé pour représenter l’apostrophe latine, en français par exemple, de façon plus élégante que par l’apostrophe de l’anglais, qui s’accommode bien de sa laideur parce qu’il l’utilise fort peu.

Pour la notation décimale des codes, la valeur binaire de chaque octet est convertie en base 10, ce qui donne un nombre compris entre 0 et 255, ainsi par exemple pour È :

(c3)16 = (11000011)2 = (195)10
(88)16 = (10001000)2 = (136)10

Le code hexadécimal c388 est fourni par la table de caractères, le code UTF-8 de È est donc (1100001110001000)2. C’est parce que 16 est une puissance de 2 que le code hexadécimal est obtenu simplement par la concaténation des conversions en base 16 de chaque octet. La notation hexadécimale est expliquée plus en détail ici.

Rien dans le texte binaire ne permet de détecter quel codage est utilisé, cette information doit être fournie explicitement par l’auteur du document (ou par son logiciel).

 Richesse et difficultés d’UTF-8

À l’époque d’Ascii et d’EBCDIC la vie était simple, du moins pour les anglophones qui se contentent de l’alphabet latin sans accents ni autres signes diacritiques, ou en d’autres termes sans caractères composés (é est le caractère composé de e et de l’accent aigu). Des bricolages inavouables ont permis de coder sur un octet la plupart des autres écritures alphabétiques, telles que les alphabets latin avec signes diacritiques, cyrillique, arabe, hébreu, grec : en effet un octet de huit bits peut représenter 256 signes. Dans ce monde, une suite de n octets pouvait représenter une chaîne de n caractères, soit un texte lisible à l’écran par un humain.

Mais pour les locuteurs de langues écrites en sinogrammes ou en écriture devanagari il n’en allait pas ainsi, ce pourquoi on a inventé Unicode et UTF-8, cf. ci-dessus. Du coup le codage de ces écritures ne respecte plus la correspondance d’un octet pour un caractère, ce qui complique énormément le traitement des textes. Manuel Serrano, auteur du compilateur Scheme Bigloo, m’a dit que l’adaptation à UTF-8 avait été une des transitions les plus difficiles qu’il ait eues à effectuer. Une chaîne de n caractères peut avoir une longueur en octets variable selon l’alphabet, et peu prévisible pour qui ignore UTF-8. Ainsi en Scheme avec Bigloo, et pour les écritures latine, bengali, éthiopienne et chinoise :

  1. 1:=> (string-length "abcdef")
  2. 6
  3. 1:=> (string-length "abcdeট")
  4. 8
  5. 1:=> (string-length "abcdéf")
  6. 7
  7. 1:=> (string-length "abcdeቐ")
  8. 8
  9. 1:=> (string-length "abcde䢔")
  10. 8

Télécharger

 Les caractères de Rust et les séquences biologiques

Rust ne connaît que les caractères UTF-8. Je croyais qu’ils étaient tous sur quatre octets, avec l’avantage que procureraient la simplicité et l’uniformité, mais c’est comme en Scheme, ce que me fait remarquer, en lecteur avisé, Bastien Vigneron (cf. aussi les commentaire de Martin Larralde à la fin de l’article) :

  1. fn main() {
  2.     let hello = "hello";
  3.     println!("size of {} : {}", hello, hello.len());
  4.  
  5.     let helloRussian = "Привет";
  6.     println!("size of {} : {}", helloRussian, helloRussian.len())
  7. }
  8.  
  9. size of hello : 5
  10. size of Привет : 12

Télécharger

Pour les biologistes et les chimistes, les séquences nucléiques sont écrites dans un alphabet de quatre caractères, ATGC pour l’ADN, AUGC pour l’ARN. Les séquences protéiques sont écrites dans un alphabet plus complexe, de vingt acides aminés (22 si l’on en compte deux très rares). Les banques de séquences comportent également des identifiants, des références bibliographiques et d’autres informations (features), toujours écrites en anglais, donc à l’origine codées en Ascii.

Une séquence biologique est donc une chaîne, potentiellement très longue, de caractères pris dans un alphabet simple. On trouve en effet dans les banques de séquences nucléiques des génomes bactériens entiers, soit des millions de nucléotides. Traiter ces séquences en UTF-8 semble un gaspillage éventuellement important. C’est pourquoi j’ai tenté d’écrire un programme Rust où les séquences seraient codées par des vecteurs d’octets, type de données tout à fait disponible dans le langage. Voici le résultat, et les conclusions que j’ai tirées de cette expérience.

 Les données

Voici à titre d’exemple un fichier au format FASTA qui donne le code d’un gène d’une orchidée :

  1. >gi|2765658|emb|Z78533.1|CIZ78533 C.irapeanum 5.8S rRNA gene and ITS1 and ITS2 DNA
  2. CGTAACAAGGTTTCCGTAGGTGAACCTGCGGAAGGATCATTGATGAGACCGTGGAATAAACGATCGAGTG
  3. AATCCGGAGGACCGGTGTACTCAGCTCACCGGGGGCATTGCTCCCGTGGTGACCCTGATTTGTTGTTGGG
  4. CCGCCTCGGGAGCGTCCATGGCGGGTTTGAACCTCTAGCCCGGCGCAGTTTGGGCGCCAAGCCATATGAA
  5. AGCATCACCGGCGAATGGCATTGTCTTCCCCAAAACCCGGAGCGGCGGCGTGCTGTCGCGTGCCCAATGA
  6. ATTTTGATGACTCTCGCAAACGGGAATCTTGGCTCTTTGCATCGGATGGAAGGACGCAGCGAAATGCGAT
  7. AAGTGGTGTGAATTGCAAGATCCCGTGAACCATCGAGTCTTTTGAACGCAAGTTGCGCCCGAGGCCATCA
  8. GGCTAAGGGCACGCCTGCTTGGGCGTCGCGCTTCGTCTCTCTCCTGCCAATGCTTGCCCGGCATACAGCC
  9. AGGCCGGCGTGGTGCGGATGTGAAAGATTGGCCCCTTGTGCCTAGGTGCGGCGGGTCCAAGAGCTGGTGT
  10. TTTGATGGCCCGGAACCCGGCAAGAGGTGGACGGATGCTGGCAGCAGCTGCCGTGCGAATCCCCCATGTT
  11. GTCGTGCTTGTCGGACAGGCAGGAGAACCCTTCCGAACCCCAATGGAGGGCGGTTGACCGCCATTCGGAT
  12. GTGACCCCAGGTCAGGCGGGGGCACCCGCTGAGTTTACGC

Télécharger

- gi|2765658| donne l’identifiant GenBank de la séquence ;
- emb|Z78533.1| donne son identifiant EMBL (European Molecular Biology Laboratory).

 Le programme

Ce petit programme d’exemple lit deux séquences dans des fichiers texte simples d’une seule ligne (le traitement du format FASTA reste à écrire), afin éventuellement de les aligner, mais ici et pour l’instant je me contente de les afficher. Les noms des deux fichiers qui contiennent chacun une séquence sont passés en arguments sur la ligne de commande d’invocation du programme, et lus dans une structure (struct) de type Config. Pour éviter les quatre octets du type caractère de Rust, les caractères du texte de la séquence sont déclarés du type u8 (unsigned 8), soit un type numérique de taille 1 octet.

  1. // main.rs
  2.  
  3. extern crate chaines_u8;
  4.  
  5. use chaines_u8::file_to_ascii;
  6.  
  7. fn main() {
  8.     file_to_ascii::debut();
  9. }

Télécharger

  1. // mod.rs
  2.  
  3. pub mod file_to_ascii;

Télécharger

Comme d’habitude, le plus compliqué ce sont les entrées-sorties, bien que ce ne soit que technique.

  1. // lib.rs
  2.  
  3. pub mod file_to_ascii {
  4.  
  5.     use std::u8;
  6.     use std::env;
  7.     use std::fs;
  8.     use std::fs::File;
  9.     use std::io::Read;
  10.     use std::fs::Metadata;
  11.    
  12.     pub struct Config {
  13.         pub filename1: String,
  14.         pub filename2: String,
  15.     }
  16.    
  17.     impl Config {
  18.         pub fn new(args: &[String]) -> Config {
  19.             if args.len() < 3 {
  20.                 panic!("pas assez d'arguments");
  21.             }
  22.             let filename1 = args[1].clone();
  23.             let filename2 = args[2].clone();
  24.            
  25.             Config { filename1, filename2 }
  26.         }
  27.     }
  28.  
  29.     fn get_file_names() {
  30.         let args: Vec<String> = env::args().collect();
  31.         let config = Config::new(&args);
  32.        
  33.         println!("Alignement de {} avec {} \n", config.filename1, config.filename2);
  34.        
  35.         let the_metadata1 = fs::metadata(&config.filename1).expect("illisible");
  36.         let the_metadata2 = fs::metadata(&config.filename2).expect("illisible");
  37.  
  38.         println!("Nom du fichier 1 : {} Longueur : {} \n", &config.filename1, the_metadata1.len());
  39.         println!("Nom du fichier 2 : {} Longueur : {} \n", &config.filename2, the_metadata2.len());
  40.  
  41.         let seq1 = fasta_read_seq(&config.filename1, the_metadata1);
  42.         let seq2 = fasta_read_seq(&config.filename2, the_metadata2);
  43.  
  44.         println!("Séquence 1 : {:?} \n", &seq1);
  45.         println!("Séquence 2 : {:?} \n", &seq2);
  46.     }
  47.  
  48.     fn fasta_read_seq(filename: &String, the_metadata: Metadata) -> Vec<u8> {
  49.         let mut f = File::open(&filename).expect("pas de fichier");
  50.         let mut line = vec![0; the_metadata.len() as usize];
  51.         f.read(&mut line).expect("débordement de buffer");
  52.  
  53.         line
  54.     }
  55.  
  56.     pub fn debut() {
  57.         get_file_names();
  58.     }
  59. }

Télécharger

 Exemple d’exécution et conclusion

  1. $ cargo run Data/sequence1.fasta Data/sequence2.fasta
  2.     Finished dev [unoptimized + debuginfo] target(s) in 0.00s
  3.      Running `target/debug/chaines_u8 Data/sequence1.fasta Data/sequence2.fasta`
  4. Alignement de Data/sequence1.fasta avec Data/sequence2.fasta
  5.  
  6. Nom du fichier 1 : Data/sequence1.fasta Longueur : 16
  7.  
  8. Nom du fichier 2 : Data/sequence2.fasta Longueur : 13
  9.  
  10. Séquence 1 : [71, 65, 84, 84, 67, 71, 65, 84, 84, 65, 84, 65, 67, 71, 65, 10]
  11.  
  12. Séquence 2 : [71, 71, 65, 65, 84, 67, 71, 65, 84, 65, 84, 65, 10]

Télécharger

Comme les caractères des séquences sont de type unsigned 8, ils apparaissent naturellement sous forme numérique, il faudrait une fonction de transcodage pour les afficher sous forme de texte alphabétique.

Quelle conclusion tirer de cette expérience ? Est-ce se compliquer la vie inutilement ? De nos jours l’espace en mémoire ou sur disque n’est plus une denrée aussi rare que dans les années 1970, et appliquer un algorithme d’alignement de séquences à des génomes entiers de plusieurs millions de nucléotides ne semble pas un exercice raisonnable (mais ici les biologistes me contrediront peut-être).

Les commentaires de Bastien Vigneron ci-dessus et de Martin Larralde ci-dessous me suggèrent qu’UTF-8 n’est pas vraiment une bonne idée et que je devrais persister pour un type Vec. En effet, la question n’est pas tant celle de la place mémoire que celle de sa variabilité : avoir des chaînes de longueurs variables et, surtout, imprévisibles est supportable pour de l’édition de textes, mais pas pour du calcul.