Découverte :
L'indice de Jaccard, pas qu'une histoire de mailles...

J'ai utilisé dernièrement l'indice de Jaccard pour comparer des ensembles de mots. Comme c'est une mesure assez classique et plutôt utile, j'ai décidé de vous en parler un peu. Donc voici une introduction à l'indice de Jaccard, à ne pas confondre avec le pull Jacquard, ce n'est pas du tout la même chose.

Pull Jaquard by wildmary (CC BY-NC-SA 2.0)

Pull Jacquard by wildmary (CC BY-NC-SA 2.0)

L'indice de Jaccard est une mesure simple de similarité entre deux ensembles d'objets proposée par Paul Jaccard en 1901 [1,2]. Il consiste à diviser le nombre d'objets en commun par le nombre d'objets distincts dans les deux ensembles, autrement dit le cardinal de l'intersection divisé par le cardinal de l'union ou encore :

Formule de Jaccard

Formule de Jaccard

"Pourquoi je vous parle de ce truc là sur un blog de bioinformatique ?" me demanderez-vous. Et je vous répondrai : "Parce que cela m'a servi dans mon boulot de bioinformaticien." Je vous explique...

En ce moment, je fais de la reconstruction automatique de réseaux métaboliques. Cela consiste, à partir d'un génome annoté, à retrouver les réactions biochimiques qui correspondent aux gènes. Pour cela, j'utilise le logiciel Pathway Tools, qui utilise lui-même trois types d'annotations pour associer une réaction biochimique à un gène : le numéro EC (classification des enzymes), les termes Gene Ontology, et la description de la fonction.

Pour les numéros EC, l'association est assez simple : si un gène est annoté par un EC et qu'une réaction chimique possède ce même EC, alors on associe la réaction au gène concerné. Pour les termes GO, cela peut être un peu plus compliqué, les termes GO un peu trop génériques sont ignorés. Enfin, pour les descriptions de fonction, Pathway Tools semble utiliser un comparateur exact. Si la description de la fonction diffère d'un seul caractère, elle est rejetée.

Ce comparateur exact est un peu frustrant car certaines descriptions de fonctions sont générées automatiquement et peuvent donc être proches mais différentes. Par exemple : "3-ketoacyl-acyl carrier protein synthase," "β-ketoacyl acyl carrier protein synthase," "β-ketoacyl-[acyl carrier protein] synthase." Tous ces termes sont équivalents (même numéro EC) mais ne passent pas le comparateur exact.

Je me suis alors souvenu de l'indice de Jaccard, qui permet de comparer des ensembles de mots (un ami l'avait utilisé pour ça). Appliquons donc l'indice de Jaccard sur ce dernier exemple pour voir comment ça marche.

J'ai commencé par enlever tous les signes de ponctuation, on a donc les deux ensembles de mots suivants :

  • "3-ketoacyl-acyl carrier protein synthase" devient {"3", "ketoacyl", "acyl", "carrier", "protein", "synthase"}
  • "β-ketoacyl acyl carrier protein synthase" devient {"β", "ketoacyl", "acyl", "carrier", "protein", "synthase"}
  • "β-ketoacyl-[acyl carrier protein] synthase" devient {"β", "ketoacyl", "acyl", "carrier", "protein", "synthase"}

Ainsi, si on calcule l'indice de Jaccard entre les deux premiers ensembles, on obtient 5/7 = 0,71, entre les deux derniers : 7/7 = 1,0. Drôlement pratique non ? Bon par contre, tout n'est pas toujours aussi facile. Ici, on ne tient pas compte de la fréquence ou de la taille des mots, ce qui peut-être utile dans certains cas.

Pour aller plus loin

C'était une illustration super simpliste de cette mesure, mais voici quelques liens sur l'utilisation de l'indice de Jaccard en biologie et en bioinformatique qui peuvent vous inspirer :

J. M. Duarte, J. B. dos Santos, and  L. C. Melo. Comparison of similarity coefficients based on RAPD markers in the common bean. Genet. Mol. Biol. [online]. 1999, vol.22, n.3

Lewis SN, Nsoesie E, Weeks C, Qiao D, Zhang L (2011) Prediction of Disease and Phenotype Associations from Genome-Wide Association Studies. PLoS ONE, 6(11): e27175. doi:10.1371/journal.pone.0027175

A. Baselga, and C. D. L. Orme, betapart: an R package for the study of beta diversity. Methods in Ecology and Evolution, Vol. 3(5), pp. 808-812 (2012)

A. Rau, M. Gallopin, G. Celeux, and F. Jaffrézic, Data-based filtering for replicated high-throughput transcriptome sequencing experiments. Bioinformatics, published online on 2 July, 2013.

Références

[1] P. Jaccard, Distribution de la flore alpine dans le bassin des Dranses et dans quelques régions voisines. Bulletin de la Société Vaudoise des Sciences Naturelles, Vol. 37, pp. 241-272 (1901).

[2] R. Real, and J.M. Vargas, The Probabilistic Basis of Jaccard's Index of Similarity. Systeme Biology, Vol. 45 (3), pp. 385-390 (1996).

Merci à Bu, Clem_ et Mica pour leur relecture.

  • À propos de
  • Je suis actuellement en post-doc dans l'équipe DYLISS de L'IRISA à Rennes. Je travaille sur la reconstruction automatique de réseaux métaboliques. Plus particulièrement, je m'intéresse aux aspects fouille de connaissance, combinatoire, base de données en graphe. Mais dans un passé pas si lointain, je me suis aussi intéressé aux séquences de protéines, à leur alignement et à la prédiction de leur structures.

2 commentaires sur “L'indice de Jaccard, pas qu'une histoire de mailles...

  1. Les mesures comme l\'indice de Jaccard ou le coefficient de Dice marchent bien à condition que les éléments de l\'ensemble soient indépendant ET équiprobable. Si ce n\'est pas le cas, on introduit un biais. Par exemple sur des ensembles de mots, les mots courant (\"et\", \"le\", \"la\",...) comptent autant que d\'autres comme \"méthylation\" ou \"apoptose\", ce qui est dommage (deux texte qui ont \"les\" en commun sont peut-être moins similaires que deux textes qui parlent d\'apoptose). Des stratégies classiques pour contourner ça sont basées sur la fréquence (les mots fréquents en général sont moins informatifs et sont donc pénalisés, cf la notion d\'information content) ou sur la granularité... mais c\'est une autre histoire

  2. Pour information, l\'indice de Jaccard est également utilisé en bioinformatique pour la comparaison de groupes d\'orthologues obtenus avec différentes méthodes. Si le sujet vous intéresse je vous conseille également de vous renseigner sur le \"gain d\'information\".
    Cécile

Répondre à cecile Annuler la réponse.