Découverte :
Filtre de Bloom

Filtre à café, Elya (CC-BY-SA-3.0)

Elke Wetzig, Elya (CC-BY-SA-3.0), via Wikimedia Commons

Comme vous le savez sans doute, la génomique tend à générer de plus en plus de données grâce à une forte réduction des coûts (cf graphique ci dessous). Depuis peu de temps, la génération des données n’est plus forcement le point limitant d’une étude, mais c’est l’analyse des données qui devient vraiment longue et coûteuse. De ce fait, les nouveaux logiciels que nous autre, bio-informaticien(ne)s, sommes amené(e)s à développer doivent prendre cette évolution en compte. Si on peut parfois accepter de prendre 128Go de RAM et laisser tourner un logiciel pendant une semaine, il est quand même plus agréable de pouvoir faire la même chose sur son ordinateur portable en un quart d'heure. Heureusement, des astuces existent pour réduire les temps de calcul ! Dans cet article, je présente une structure de données de plus en plus utilisé dans le domaine de la bio-informatique2-3-4 car très compacte en mémoire et rapide à l'exécution : le filtre de Bloom1.

Coût d'un Megabase

http://www.genome.gov/sequencingcosts/

Il s'agit d'une structure de données probabiliste qui sert à tester si un élément fait partie d'un ensemble de données ou non. Probabiliste car cette structure peut générer des faux positifs et ne peut donc pas s'adapter à n'importe quelle application ou type de données. On évitera par exemple d'utiliser une structure de données pouvant donner des faux positifs pour un robot d'opérations à cœur ouvert ou de système de guidage de missiles. En revanche, dès lors qu'on travaille sur de grands ensembles de données et qu'on peut accepter, disons, 0,1% de faux positifs, comme dans le comptage de k-mers1 ou la correction d'erreurs2 dans de très gros jeux de données de séquençage, le filtre de Bloom est très intéressant car rapide en temps d'exécution et compacte en mémoire.

Les fonctions de hachage

Avant d'expliquer plus en détail le filtre de Bloom, il est nécessaire de connaitre le principe des fonctions de hachage. Ce type de fonction permet de "hacher" un contenu pour fournir en sortie une chaîne de caractères représentant la donnée initiale. Une des fonctions de hachage les plus courante est celle nommé MD5 (Message Digest 5). Cette fonction permet de calculer une chaîne de 32 caractères alpha-numériques à partir de n'importe quel fichier en entrée. Par exemple, le résultat de la fonction MD5 sur “azerty”  est “ab4f63f9ac65152575886860dde480a1”. Le résultat sur le fichier d'installation de la dernière version d'Ubuntu (ubuntu-12.04-desktop-i386-fr.iso) est “898c6fe424296d70058a742b51- e7f730”.

Il est important de comprendre deux choses. Premièrement les fonctions de hachage donnent généralement en sortie une chaîne de caractère de longueur fixe (32 pour le MD5). Et deuxièmement, comme l'ensemble d'arrivé est fini (il n'y a pas une infinité de chaînes de 32 caractères), il y a forcément des “collisions”, c'est à dire que deux messages différents donnent le même résultat. On peut donc voir une fonction de hachage comme un moyen de passer d'un ensemble de taille X à un ensemble plus petit mais comportant des collisions.

Le filtre de Bloom en détail

Avant de continuer, il faut garder en tête que le filtre de Bloom ne vous permet pas vraiment de “stocker” des données à proprement parler ; le filtre est la pour vous permettre de tester l'appartenance d'un élément à un ensemble de données. Pour la suite des explications, j'utiliserai des séquences ADN en tant que données, mais vous verrez que vous pouvez utiliser à 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 parti. Pour mettre en mémoire une séquence, nous allons utiliser plusieurs fonctions de hachage indépendantes qui retourneront une suite de bits correspondant à des adresses mémoires : au lieu d'effectivement stocker les données, on ne stockera ainsi que quelques bits d'information. Pour ne pas vous perdre, je vais faire un exemple très simplifié. Imaginons 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 initialement vide. On peut le représenter comme un tableau de bits dont tous les bits sont à 0 :

Etat initial : filtre de Bloom vide

État initial : le filtre est vide. Nico M. (CC-by-SA 2.0)

 

Prenons la première la séquence à mettre en mémoire, AGTG. On utilise deux fonctions de hachage indépendantes sur cette séquence. Chaque fonction retourne une chaîne de 3 bits. La première fonction va nous donner pour AGTCG, 011 et la seconde, 101. On va alors changer les bits du tableau à ces adresses. Voici son nouveau contenu :

Filtre de Bloom après premier remplissage

Premier remplissage. Nico M. (CC-by-SA 2.0)

Nous allons maintenant insérer la seconde séquence, GTACTAT. La séquence est plus longue mais nos fonctions de hachage retournent toujours une chaîne de 3 bits. La première fonction va nous retourner 001 et la seconde, 110. On va donc mettre le tableau à jour :

Filtre de Bloom après second remplissage

Second remplissage. Nico M. (CC-by-SA 2.0)

Le filtre de Bloom ainsi créé représente l'ensemble A.

2. Interrogation du filtre de Bloom

Maintenant, nous allons regarder si les séquences de l'ensemble B sont dans notre filtre. Nous allons utiliser les mêmes fonctions. On va donc avoir de nouveau, pour AGTG : 011 et 101. On va alors lire dans le filtre à ces adresses :

Vérification de valeur dans le filtre : ok

Vrai positif. Nico M. (CC-by-SA 2.0)

Si tous les bits sont bien à 1, la séquence AGTG est probablement dans notre ensemble de séquences A.

 

Si Maintenant on test TTGC, la première fonction va par exemple donner 111 et la seconde 011.

Vérification de valeur dans le filtre : faux !

Vrai négatif. Nico M. (CC-by-SA 2.0)

On voit dans notre filtre qu'au moins un bit est à 0, on peut alors dire de manière certaine (aucun faux négatif n'est possible) que TTGC n'est pas dans l'ensemble A.

 

Finalement, on va tester TGATT. Là, malheureusement, nos fonctions de hachage trop simplistes créent des collisions. Par exemple, la première fonction va donner 011 (comme pour AGTCG) et la seconde 110 (comme pour GTACTAT). En regardant dans le filtre,

Vérification de valeur dans le filtre : faux positif

Faux positif. Nico M. (CC-by-SA 2.0)

on voit que toutes les positions sont à 1 ; on va donc considérer, à tord, que TGATT est présente dans le filtre : c'est un faux positif. Vous aurez compris que le nombre de faux positifs est fortement lié à l'occupation du tableau.

Pour conclure...

Voilà pour cette introduction aux filtres de Bloom. De nombreuses autres choses restent à dire, comme par exemple sur l'estimation du nombre de faux-positifs, sur la taille à donner au filtre, sur les fonctions de hachage à utiliser (jetez un œil aux fonctions de Jenkins et à celles de Kirsch et Mitzenmacher5)... Ceci fera peut-être l'objet d'un prochain article 😉

Pour aller plus loin : 

1. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM (1970) vol. 13 (7) pp. 422-426

2. Melsted et Pritchard. Efficient counting of k-mers in DNA sequences using a bloom filter. BMC bioinformatics (2011) vol. 12 (1) pp. 333

3. Liu et Schmidt. DecGPU: distributed error correction on massively parallel graphics processing units using CUDA and MPI. BMC bioinformatics (2011)

4. Pell et al. Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Arxiv preprint arXiv:1112.4193 (2011)

5. Kirsch et Mitzenmacher. Less hashing, same performance: Building a better Bloom filter. Algorithms–ESA 2006 (2006) pp. 456-467

  • À propos de
  • Après un DUT informatique et une licence Mathématiques, Informatique et Statistique, j'ai poursuivi en Master de Modélisation des Systèmes Biologiques, parcours bio-informatiques, à Rennes, puis en thèse à l'IRISA-INRIA de Rennes sur une problématique de création d'algorithmes pour l'étude de métagénomique de novo. J'ai ensuite fait un postdoc à la "Stazione Zoologica Anton Dohrn" de Naples, sur des problématiques mêlant métagénomique, océanographie et Tara Oceans. Je suis maintenant ingénieur de recherche à l'Institut Pasteur (HUB).

4 commentaires sur “Filtre de Bloom

  1. Excellent 🙂 Même si ce n\'est pas du tout mon domaine, j\'ai trouvé cette promenade très intéressante.

  2. Excellent article! Ca m\'a permis de mieux comprendre le filtre de Bloom que j\'aurais à utiliser pour un projet en big data. Merci

    • Merci, content d\'aider 🙂

  3. Cool 😀

Laisser un commentaire