Graphe de de Bruijn

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur n-1 entre tous les mots de longueur n sur un alphabet donné. Les graphes sont nommés ainsi d'après le mathématicien Nicolaas Govert de Bruijn qui les a décrits en 1946[1]. Les graphes ont déjà été décrits antérieurement, notamment par Camille Flye Sainte-Marie en 1894[2] et par Irving J. Good en 1946[3],[4].

Le graphe de de Bruijn B(k,n) d'ordre n sur un alphabet A à k lettres est construit comme suit. Les sommets B(k,n) sont en bijection avec (sont étiquetés par) les k^n mots de longueur n sur A. Si u et v sont deux sommets, il y a un arc de u à v si le mot obtenu en supprimant la première lettre de u est le même que le mot obtenu en supprimant la dernière lettre de v; en d'autres termes, s'il existe deux lettres a et b, et un mot x, tels que u=ax et v=xb. La présence d'un arc signifie donc un chevauchement maximal entre mots de même longueur.

Graphe de de Bruijn B(2,3) construit sur l'alphabet binaire (k=2) pour des mots de longueur n=3.

Exemples[modifier | modifier le code]

Le graphe B(2,3) ci-contre est construit sur un alphabet binaire A=\{0, 1\} pour des mots de longueur n=3. Les 2^3=8 mots de longueur 3 sur l'alphabet binaire sont :

000,\ 001,\ 010,\ 011,\ 111,\ 110,\ 101,\ 100.

Il existe par exemple un arc allant du sommet 000 au sommet 001 car le suffixe de longueur 2 de 000 est égal au préfixe de longueur 2 de 001. De même, il existe un arc allant du sommet 100 au sommet 000 car le suffixe de longueur 2 de 100 est égal au préfixe de longueur 2 de 000.

Le graphe B(n,1) est formé de n sommets, un pour chaque lettre. De chaque sommet partent n arcs, il y a donc n^2 arcs.

Propriétés[modifier | modifier le code]

  • Le graphe B(k,n) d'ordre n est le line graph du graphe B(k,n-1) d'ordre n-1 :

Systèmes dynamiques[modifier | modifier le code]

On peut dessiner un graphe de de Bruijn binaire comme sur la partie gauche de la figure, de telle sorte qu'il ressemble à un objet de la théorie des systèmes dynamiques, comme l'attracteur de Lorenz affiché à droite.

DeBruijn-3-2.svg         Lorenz attractor yb.svg

Cette analogie s'explique simplement : le graphe de de Bruijn B(k,n) est un modèle de décalage de Bernoulli

x\mapsto kx\ \bmod\ 1

Le décalage de Bernoulli, (aussi appelé la fonction 2x mod 1 ou fonction dyadique pour k=2) est un système dynamique ergodique que l'on peut voir comme un opérateur de décalage sur un nombre k-adique. Les trajectoires de ce système dynamique correspondent aux chemins dans le graphe de de Bruijn, avec la correspondance qui associe à chaque réel x de l'intervalle semi-ouvert [0,1[ le somme du graphe qui correspond aux n premiers chiffres dans la représentation de x en base k. De manière équivalente, les chemins dans le graphe de de Bruijn correspondent aux trajectoires d'un système dynamique de type fini.

Utilisation[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Nicolaas Govert de Bruijn, « A Combinatorial Problem », Koninklijke Nederlandse Akademie v. Wetenschappen, vol. 49,‎ 1946, p. 758–764
  2. Camille Flye Sainte-Marie, « Question 48 », L'Intermédiaire des Mathématiciens, vol. 1,‎ 1894, p. 107–110
  3. Irving J. Good, « Normal recurring decimals », Journal of the London Mathematical Society, vol. 21, no 3,‎ 1946, p. 167–169 (DOI 10.1112/jlms/s1-21.3.167)
  4. Pour un historique plus précis, on peut consulter : Jean Berstel et Dominique Perrin, « The origins of combinatorics on words », European Journal of Combinatorics, vol. 28, no 3,‎ 2007, p. 996–1022 (DOI 10.1016/j.ejc.2005.07.019, lire en ligne)
  5. Pavel A. Pevzner, Haixu Tang et Michael S. Waterman, « An Eulerian path approach to DNA fragment assembly », Proceedings of the National Academy of Sciences, vol. 98, no 17,‎ 2001, p. 9748–9753 (PMID 11504945, PMCID 55524, DOI 10.1073/pnas.171285098, Bibcode 2001PNAS...98.9748P)
  6. Pavel A. Pevzner et Haixu Tang, « Fragment Assembly with Double-Barreled Data », Bioinformatics/ISMB, vol. 1,‎ 2001, p. 1–9
  7. Daniel R. Zerbino et Ewan Birney, « Velvet: algorithms for de novo short read assembly using de Bruijn graphs », Genome Research, vol. 18, no 5,‎ 2008, p. 821–829 (PMID 18349386, PMCID 2336801, DOI 10.1101/gr.074492.107)