de Bruijnグラフの圧縮

摘要

We propose a new succinct de Bruijn graph representation. If the de Bruijn graph of k-mers in a DNA sequence of length N has m edges, it can be represented in 4m + o(m) bits. This is much smaller than existing ones. The numbers of outgoing and incoming edges of a node are computed in constant time, and the outgoing and incoming edge with given label are found in constant time and O(k) time, respectively. The data structure is constructed in O(N k log m/log log m) time using no additional space.%本稿はde Bruijn グラフの新しい簡潔表現を提案する.長さ N の DNA配列の k-mer に対する de Bruijn グラフが m 本の枝を持つとき，このグラフは 4m + o(m) ビットで表現できる.節点の出次数と入次数は定数時間，ある節点から出る，またはある節点に入る枝で指定されたラベルを持つものはそれぞれ定数時間，O(k)時間で求まる.データ構造は余分な作業領域を使わずに O(Nk log m/log log m) 時間で構築できる.