de Bruijnグラフの圧縮
スポンサーリンク
概要
- 論文の詳細を見る
本稿はde Bruijnグラフの新しい簡潔表現を提案する.長さNのDNA配列のκ-merに対するde Bruijnグラフがm本の枝を持つとき,このグラフは4m+o(m)ビットで表現できる.節点の出次数と入次数は定数時間,ある節点から出る,またはある節点に入る枝で指定されたラベルを持つものはそれぞれ定数時間,O(κ)時間で求まる.データ構造は余分な作業領域を使わずに0(Nκlogm/loglog m)時間で構築できる.
- 一般社団法人電子情報通信学会の論文
- 2012-08-27