Grafic de de Bruijn

Grafic de de Bruijn (2, 3)

Un grafic de Bruijn este un tip de digraf utilizat în teoria sistemelor și bioinformatică .

Descoperit independent de de Bruijn și Good , un grafic $dB(m,n)$ ${\ displaystyle dB (m, n)}$ ${\ displaystyle dB (m, n)}$ este compus plecând de la unalfabet de cardinalitate $m$ ${\ displaystyle m}$ $m$ și un număr întreg $n$ ${\ displaystyle n}$ $n$ . Graficul deține $m^{n}$ ${\ displaystyle m ^ {n}}$ $m ^ n$ vârfuri care conțin toate secvențele de lungime $n$ ${\ displaystyle n}$ $n$ (numite secvențe de Bruijn).

Este $S=\left\{s_{1},\ldots ,s_{m}\right\}$ ${\ displaystyle S = \ left \ {s_ {1}, \ ldots, s_ {m} \ right \}}$ ${\ displaystyle S = \ left \ {s_ {1}, \ ldots, s_ {m} \ right \}}$ alfabetul simbolurilor și ambele $S^{n}=V=\left\{(s_{1},\ldots ,s_{1}),(s_{1},\ldots ,s_{2}),\ldots ,(s_{m},\ldots ,s_{m})\right\}$ ${\ displaystyle S ^ {n} = V = \ left \ {(s_ {1}, \ ldots, s_ {1}), (s_ {1}, \ ldots, s_ {2}), \ ldots, (s_ {m}, \ ldots, s_ {m}) \ right \}}$ ${\ displaystyle S ^ {n} = V = \ left \ {(s_ {1}, \ ldots, s_ {1}), (s_ {1}, \ ldots, s_ {2}), \ ldots, (s_ {m}, \ ldots, s_ {m}) \ right \}}$ de Bruijn's dictionary of sequences in length $n$ ${\ displaystyle n}$ $n$ .

Setul de arce ale graficului de Bruijn este definit de $E=\left\{\left((v_{1},v_{2},\ldots ,v_{m}),(v_{2},\ldots ,v_{m},s_{i})\right):i=1,\ldots ,m\right\}$ ${\ displaystyle E = \ left \ {\ left ((v_ {1}, v_ {2}, \ ldots, v_ {m}), (v_ {2}, \ ldots, v_ {m}, s_ {i} ) \ right): i = 1, \ ldots, m \ right \}}$ ${\ displaystyle E = \ left \ {\ left ((v_ {1}, v_ {2}, \ ldots, v_ {m}), (v_ {2}, \ ldots, v_ {m}, s_ {i} ) \ right): i = 1, \ ldots, m \ right \}}$ .