デ・ブルイングラフ

グラフ理論において、m個の記号からなるn次元デ・ブルイングラフは、記号列間の重なりを表す有向グラフです。m個^の頂点を持ち、与えられた記号の可能なすべての長さnのシーケンスで構成されます。同じ記号がシーケンス内に複数回出現することもあります。m個の記号の集合S = { s ₁ , …, s _m }の場合、頂点の集合は次のようになります。

${\displaystyle V=S^{n}=\{(s_{1},\dots ,s_{1},s_{1}),(s_{1},\dots ,s_{1},s_{2}),\dots ,(s_{1},\dots ,s_{1},s_{m}),(s_{1},\dots ,s_{2},s_{1}),\dots ,(s_{m},\dots ,s_{m},s_{m})\}.}$

頂点の 1 つを、そのすべての記号を 1 つ左にずらし、その頂点の末尾に新しい記号を追加することによって別の頂点として表現できる場合、後者の頂点は前者の頂点への有向辺を持つ。したがって、弧 (つまり、有向辺) の集合は次のようになる。

${\displaystyle E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_{i}\in S,1\leq i\leq n,1\leq j\leq m\}.}$

De Bruijn グラフはNicolaas Govert de Bruijnにちなんで命名されていますが、de Bruijn ^{[ 1 ]}とIJ Good の両方によって独立して発明されました。^{[ 2 ]}ずっと以前に、 Camille Flye Sainte-Marie ^{[ 3 ]}はそれらのプロパティを暗黙的に使用していました。

• n = 1の場合、任意の 2 つの頂点が辺を形成するという条件は自明に成り立ち、したがってすべての頂点が接続され、合計m ²本の辺が形成されます。
• 各頂点には、正確にm個の入力エッジとm個の出力エッジが存在する。
• 各n次元 De Bruijn グラフは、同じ記号セットを持つ( n − 1)次元De Bruijn グラフの線グラフである。 ^{[ 4 ]}
• 各デ・ブルイングラフはオイラーグラフであり、ハミルトングラフでもある。これらのグラフのオイラー閉路とハミルトン閉路（線グラフ構成により互いに等価）はデ・ブルイン列である。

3つの最小のバイナリDe Bruijnグラフの線グラフ構成を以下に示します。図からわかるように、n次元De Bruijnグラフの各頂点は( n -1)次元De Bruijnグラフの辺に対応し、 n次元De Bruijnグラフの各辺は( n -1)次元De Bruijnグラフの2辺パスに対応します。

バイナリ・デ・ブルイングラフは、ローレンツアトラクターなど、力学系の理論における対象に似た形で描画することができる。

バイナリ・デ・ブルイングラフ

ローレンツアトラクター

この類推は厳密に行うことができる。n次元mシンボルのデ・ブルイングラフはベルヌーイ写像のモデルである。

${\displaystyle x\mapsto mx\ {\bmod {\ }}1.}$

ベルヌーイ写像（m = 2の場合は2 x mod 1写像とも呼ばれる）は、 m進数の単一のシフトとして理解できるエルゴード的力学系である。^{[ 5 ]}この力学系の軌跡は、デ・ブルイン グラフのウォークに対応しており、その対応は、区間[0,1)の各実数xを、 xの基数m表現の最初のn桁に対応する頂点にマッピングすることによって与えられる。同様に、デ・ブルイン グラフのウォークは、有限型の片側部分シフトの軌跡に対応する。

このような埋め込みは、バイナリ デ ブルイン グラフのキュー番号が2 であること^{[ 6 ]}と、本の厚さが最大 ​​5 であることを示すために使用できます^{。 [ 7 ]}

• 一部のグリッド ネットワークトポロジは De Bruijn グラフです。
• 分散ハッシュ テーブルプロトコルKoorde はDe Bruijn グラフを使用します。
• バイオインフォマティクスでは、De Bruijnグラフは、シーケンスリードをゲノムにde novoアセンブリするために使用されます。^{[ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ]}上記のすべての可能なk-merを含む完全なDe Bruijnグラフの代わりに、de novoシーケンスアセンブラは、シーケンスデータセットで観察されたk-merのみを含むDe Bruijnサブグラフを使用します。
• 時系列予測では、観測値の離散サブシーケンス（n-グラム）をグラフノードにマッピングすることで、デ・ブルイングラフが時間的パターンを符号化するように適応されています。これにより、記号的または離散化された時系列データにおけるシーケンス依存性のモデリングが可能になります。^{[ 13 ] [ 14 ]}多変量デ・ブルイングラフは、複数の相関変数にわたるパターンを共同で符号化することでこのアイデアを拡張し、多変量時系列における複雑な変数間の時間的ダイナミクスの表現を可能にします。^{[ 15 ]}

• デ・ブルイン・トーラス
• ハミンググラフ
• カウツグラフ

• Homolog.usによるバイオインフォマティクスにおけるデ・ブルイングラフの使用に関するチュートリアル
• Kurban Intelligence Lab によるDe Bruijn Graph アルゴリズムのチュートリアル