De Bruijn Graph on:
[Wikipedia]
[Google]
[Amazon]
:
The_Bernoulli_map_(also_called_the__map_for_)_is_an_ergodic_dynamical_system,_which_can_be_understood_to_be_a_single_shift_operator">shift_of_a_p-adic">-adic_number.
In
:
The_Bernoulli_map_(also_called_the__map_for_)_is_an_ergodic_dynamical_system,_which_can_be_understood_to_be_a_single_shift_operator">shift_of_a_ ,_1)^\infty
:_x_\mapsto_(x_0,_x_1,_x_2,__...graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, an -dimensional De Bruijn graph of symbols is a directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of symbols the set of vertices is:
:
If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex. Thus the set of arcs (that is, directed edges) is
:
Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties.
Properties
* If , then the condition for any two vertices forming an edge holds vacuously, and hence all the vertices are connected, forming a total of edges. * Each vertex has exactly incoming and outgoing edges. * Each -dimensional De Bruijn graph is the line digraph of the De Bruijn graph with the same set of symbols. * Each De Bruijn graph is Eulerian andHamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
. The Euler cycles and Hamiltonian cycles of these graphs (equivalent to each other via the line graph construction) are De Bruijn sequence
In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subseq ...
s.
The line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
construction of the three smallest binary De Bruijn graphs is depicted below. As can be seen in the illustration, each vertex of the -dimensional De Bruijn graph corresponds to an edge of the De Bruijn graph, and each edge in the -dimensional De Bruijn graph corresponds to a two-edge path in the De Bruijn graph.
Dynamical systems
Binary De Bruijn graphs can be drawn in such a way that they resemble objects from the theory ofdynamical system
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in ...
s, such as the Lorenz attractor:
This analogy can be made rigorous: the -dimensional -symbol De Bruijn graph is a model of the Bernoulli map
The dyadic transformation (also known as the dyadic map, bit shift map, 2''x'' mod 1 map, Bernoulli map, doubling map or sawtooth map) is the mapping (i.e., recurrence relation)
: T: , 1) \to ,_1)^\infty
:_x_\mapsto_(x_0,_x_1,_x_2,__...
:
The_Bernoulli_map_(also_called_the__map_for_)_is_an_ergodic_dynamical_system,_which_can_be_understood_to_be_a_single_ ,_1)^\infty
:_x_\mapsto_(x_0,_x_1,_x_2,__...: The Bernoulli map (also called the map for ) is an ergodic">, 1)^\infty : x \mapsto (x_0, x_1, x_2, ...
: The Bernoulli map (also called the map for ) is an ergodic dynamical system, which can be understood to be a single shift operator">shift of a p-adic">-adic number. The trajectories of this dynamical system correspond to walks in the De Bruijn graph, where the correspondence is given by mapping each real in the interval to the vertex corresponding to the first digits in the Radix">base- representation of . Equivalently, walks in the De Bruijn graph correspond to trajectories in a one-sided subshift of finite type.
Embeddings resembling this one can be used to show that the binary De Bruijn graphs have queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defi ...
2 and that they have book thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie ...
at most 5.
Uses
* Some grid network topologies are De Bruijn graphs. * Thedistributed hash table
A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table: key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The ...
protocol Koorde
In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord DHT and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets hops per node (where is the number of nodes in the ...
uses a De Bruijn graph.
* In bioinformatics, De Bruijn graphs are used for ''de novo'' assembly of sequencing reads into a genome
In the fields of molecular biology and genetics, a genome is all the genetic information of an organism. It consists of nucleotide sequences of DNA (or RNA in RNA viruses). The nuclear genome includes protein-coding genes and non-coding g ...
.
See also
* De Bruijn torus * Hamming graph * Kautz graphReferences
External links
* {{MathWorld, title=De Bruijn Graph, id=deBruijnGraphTutorial on using De Bruijn Graphs in Bioinformatics
by Homolog.us Dynamical systems Automata (computation) Parametric families of graphs Directed graphs