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 entre tous les mots de longueur 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 d'ordre sur un alphabet à lettres est construit comme suit. Les sommets de sont en bijection avec (sont étiquetés par) les mots de longueur sur . Si et sont deux sommets, il y a un arc de à si le mot obtenu en supprimant la première lettre de est le même que le mot obtenu en supprimant la dernière lettre de ; en d'autres termes, s'il existe deux lettres et , et un mot , tels que et . La présence d'un arc signifie donc un chevauchement maximal entre deux mots de même longueur.

Graphe de de Bruijn construit sur l'alphabet binaire () pour des mots de longueur .

Exemples[modifier | modifier le code]

Le graphe ci-contre est construit sur un alphabet binaire pour des mots de longueur . Les mots de longueur 3 sur l'alphabet binaire sont :

.

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

Le graphe est formé de sommets, un pour chaque lettre. De chaque sommet partent arcs, il y a donc arcs.

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

  • Le graphe d'ordre est le line graph du graphe d'ordre  :
  • Les circuits eulériens de et hamiltoniens de se correspondent par la construction du line graph. Ces circuits sont des suites de de Bruijn (en).

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 est un modèle de décalage de Bernoulli

Le décalage de Bernoulli, (aussi appelé la fonction 2x mod 1 ou fonction dyadique pour ) 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,‎ , p. 758–764
  2. Camille Flye Sainte-Marie, « Question 48 », L'Intermédiaire des Mathématiciens, vol. 1,‎ , p. 107–110
  3. Irving J. Good, « Normal recurring decimals », Journal of the London Mathematical Society, vol. 21, no 3,‎ , 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,‎ , 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,‎ , 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,‎ , 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,‎ , p. 821–829 (PMID 18349386, PMCID 2336801, DOI 10.1101/gr.074492.107)