De Bruijn graphというものがあるらしい。そのDe Bruijn graphを使ったゲノムアセンブリ法がこちらで解説されているように使われている。
String graphがどうこうと書いてあったが追いつけず確認する。
Rでは igraph に入っているらしい。
たぶんノード。m symbol
次元。n-dimention
エッジ
ならあらゆる2つのノードが
本のエッジでつながっている。
ノードはm本の入力エッジとm本の出力エッジをもつ。
n次元 de bruijn graph は n-1 次元の line graph。
オイラー路でありハミルトン路である。つまり、すべての辺と頂点を一度通る。
ちょっと頑張ってやったら、各ノードに3本入出力があって、辺の一筆書きも頂点の一筆書きもできる、はず。
library(igraph) m <- 3; n <- 2 plot(graph.de.bruijn(m, n)) title(paste("m =", m, ",", "n =", n))
