Filtre de Bloom

Comme vous le savez sans doute, la géno­mique tend à géné­rer de plus en plus de don­nées grâce à une forte réduc­tion des coûts (cf gra­phique ci des­sous). Depuis peu de temps, la géné­ra­tion des don­nées n’est plus for­ce­ment le point limi­tant d’une étude, mais c’est l’analyse des don­nées qui devient vrai­ment longue et coû­teuse. De ce fait, les nou­veaux logi­ciels que nous autre, bio-informaticien(ne)s, sommes amené(e)s à déve­lop­per doivent prendre cette évo­lu­tion en compte. Si on peut par­fois accep­ter de prendre 128Go de RAM et lais­ser tour­ner un logi­ciel pen­dant une semaine, il est quand même plus agréable de pou­voir faire la même chose sur son ordi­na­teur por­table en un quart d'heure. Heu­reu­se­ment, des astuces existent pour réduire les temps de cal­cul ! Dans cet article, je pré­sente une struc­ture de don­nées de plus en plus uti­li­sé dans le domaine de la bio-infor­ma­tique^2–3‑4 car très com­pacte en mémoire et rapide à l'exécution : le filtre de Bloom¹.

Qu'est ce que le filtre de Bloom ?

Il s'agit d'une struc­ture de don­nées pro­ba­bi­liste qui sert à tes­ter si un élé­ment fait par­tie d'un ensemble de don­nées ou non. Pro­ba­bi­liste car cette struc­ture peut géné­rer des faux posi­tifs et ne peut donc pas s'adapter à n'importe quelle appli­ca­tion ou type de don­nées. On évi­te­ra par exemple d'utiliser une struc­ture de don­nées pou­vant don­ner des faux posi­tifs pour un robot d'opérations à cœur ouvert ou de sys­tème de gui­dage de mis­siles. En revanche, dès lors qu'on tra­vaille sur de grands ensembles de don­nées et qu'on peut accep­ter, disons, 0,1% de faux posi­tifs, comme dans le comp­tage de k‑mers¹ ou la cor­rec­tion d'erreurs² dans de très gros jeux de don­nées de séquen­çage, le filtre de Bloom est très inté­res­sant car rapide en temps d'exécution et com­pacte en mémoire.

Les fonctions de hachage

Avant d'expliquer plus en détail le filtre de Bloom, il est néces­saire de connaitre le prin­cipe des fonc­tions de hachage. Ce type de fonc­tion per­met de "hacher" un conte­nu pour four­nir en sor­tie une chaîne de carac­tères repré­sen­tant la don­née ini­tiale. Une des fonc­tions de hachage les plus cou­rante est celle nom­mé MD5 (Mes­sage Digest 5). Cette fonc­tion per­met de cal­cu­ler une chaîne de 32 carac­tères alpha-numé­riques à par­tir de n'importe quel fichier en entrée. Par exemple, le résul­tat de la fonc­tion MD5 sur “azer­ty”  est “ab4f63f9ac65152575886860dde480a1”. Le résul­tat sur le fichier d'installation de la der­nière ver­sion d'Ubuntu (ubuntu-12.04-desktop-i386-fr.iso) est “898c6­fe424296d70058a742b51- e7f730”.

Il est impor­tant de com­prendre deux choses. Pre­miè­re­ment les fonc­tions de hachage donnent géné­ra­le­ment en sor­tie une chaîne de carac­tère de lon­gueur fixe (32 pour le MD5). Et deuxiè­me­ment, comme l'ensemble d'arrivé est fini (il n'y a pas une infi­ni­té de chaînes de 32 carac­tères), il y a for­cé­ment des “col­li­sions”, c'est à dire que deux mes­sages dif­fé­rents donnent le même résul­tat. On peut donc voir une fonc­tion de hachage comme un moyen de pas­ser d'un ensemble de taille X à un ensemble plus petit mais com­por­tant des col­li­sions.

Le filtre de Bloom en détail

Avant de conti­nuer, il faut gar­der en tête que le filtre de Bloom ne vous per­met pas vrai­ment de “sto­cker” des don­nées à pro­pre­ment par­ler ; le filtre est la pour vous per­mettre de tes­ter l'appartenance d'un élé­ment à un ensemble de don­nées. Pour la suite des expli­ca­tions, j'utiliserai des séquences ADN en tant que don­nées, mais vous ver­rez que vous pou­vez uti­li­ser à peu près n'importe quoi. Le but du jeu va donc être de mettre en mémoire un ensemble de séquences ADN puis d'interroger cet ensemble pour savoir si les séquences d'un autre ensemble en font par­ti. Pour mettre en mémoire une séquence, nous allons uti­li­ser plu­sieurs fonc­tions de hachage indé­pen­dantes qui retour­ne­ront une suite de bits cor­res­pon­dant à des adresses mémoires : au lieu d'effectivement sto­cker les don­nées, on ne sto­cke­ra ain­si que quelques bits d'information. Pour ne pas vous perdre, je vais faire un exemple très sim­pli­fié. Ima­gi­nons deux ensembles de séquences. L'ensemble A contient AGTG et GTACTAT. L'ensemble B contient AGTG, TTGC et TGATT.

1. Insertion dans le filtre de Bloom

Notre filtre de Bloom est ini­tia­le­ment vide. On peut le repré­sen­ter comme un tableau de bits dont tous les bits sont à 0 :

Pre­nons la pre­mière la séquence à mettre en mémoire, AGTG. On uti­lise deux fonc­tions de hachage indé­pen­dantes sur cette séquence. Chaque fonc­tion retourne une chaîne de 3 bits. La pre­mière fonc­tion va nous don­ner pour AGTG, 011 et la seconde, 101. On va alors chan­ger les bits du tableau à ces adresses. Voi­ci son nou­veau conte­nu :

Nous allons main­te­nant insé­rer la seconde séquence, GTACTAT. La séquence est plus longue mais nos fonc­tions de hachage retournent tou­jours une chaîne de 3 bits. La pre­mière fonc­tion va nous retour­ner 001 et la seconde, 110. On va donc mettre le tableau à jour :

Le filtre de Bloom ain­si créé repré­sente l'ensemble A.

2. Interrogation du filtre de Bloom

Main­te­nant, nous allons regar­der si les séquences de l'ensemble B sont dans notre filtre. Nous allons uti­li­ser les mêmes fonc­tions. On va donc avoir de nou­veau, pour AGTG : 011 et 101. On va alors lire dans le filtre à ces adresses :

Si tous les bits sont bien à 1, la séquence AGTG est pro­ba­ble­ment dans notre ensemble de séquences A.

Si Main­te­nant on test TTGC, la pre­mière fonc­tion va par exemple don­ner 111 et la seconde 011.

On voit dans notre filtre qu'au moins un bit est à 0, on peut alors dire de manière cer­taine (aucun faux néga­tif n'est pos­sible) que TTGC n'est pas dans l'ensemble A.

Fina­le­ment, on va tes­ter TGATT. Là, mal­heu­reu­se­ment, nos fonc­tions de hachage trop sim­plistes créent des col­li­sions. Par exemple, la pre­mière fonc­tion va don­ner 011 (comme pour AGTG) et la seconde 110 (comme pour GTACTAT). En regar­dant dans le filtre,

on voit que toutes les posi­tions sont à 1 ; on va donc consi­dé­rer, à tord, que TGATT est pré­sente dans le filtre : c'est un faux posi­tif. Vous aurez com­pris que le nombre de faux posi­tifs est for­te­ment lié à l'occupation du tableau.

Pour conclure…

Voi­là pour cette intro­duc­tion aux filtres de Bloom. De nom­breuses autres choses res­tent à dire, comme par exemple sur l'estimation du nombre de faux-posi­tifs, sur la taille à don­ner au filtre, sur les fonc­tions de hachage à uti­li­ser (jetez un œil aux fonc­tions de Jen­kins et à celles de Kirsch et Mit­zen­ma­cher⁵)… Ceci fera peut-être l'objet d'un pro­chain article 😉

Pour aller plus loin : 

1. Bloom. Space/​time trade-offs in hash coding with allo­wable errors. Com­mu­ni­ca­tions of the ACM (1970) vol. 13 (7) pp. 422–426

2. Mel­sted et Prit­chard. Effi­cient coun­ting of k‑mers in DNA sequences using a bloom fil­ter. BMC bio­in­for­ma­tics (2011) vol. 12 (1) pp. 333

3. Liu et Schmidt. DecG­PU : dis­tri­bu­ted error cor­rec­tion on mas­si­ve­ly paral­lel gra­phics pro­ces­sing units using CUDA and MPI. BMC bio­in­for­ma­tics (2011)

4. Pell et al. Sca­ling meta­ge­nome sequence assem­bly with pro­ba­bi­lis­tic de Brui­jn graphs. Arxiv pre­print arXiv:1112.4193 (2011)

5. Kirsch et Mit­zen­ma­cher. Less hashing, same per­for­mance : Buil­ding a bet­ter Bloom fil­ter. Algorithms–ESA 2006 (2006) pp. 456–467