de Bruijn graph によるゲノムアセンブリー

de novo アセンブリー

生物ゲノムの解読は、その生物を詳しく理解する上で欠かせない。ゲノムは、実質 DNA を指す。生物の DNA は複数の染色体に分けられて保存されている。1 本の染色体に含まれる DNA の長さは、生物種や染色体番号にもよるが、108 オーダーの塩基配列からなる。これだけ長い DNA の塩基配列をシーケンシングできる技術は、まだ開発されていない。そのため、現在では、長い DNA の塩基配列を、100 塩基前後の短い断片に切断してからシーケンシングし、次にシーケンシングされた短い断片配列を、コンピューター上で繋げていき、元の DNA 塩基配列を復元させるアプローチを取っている。このように、複数の短い塩基配列から、元の長い塩基配列を復元させることをアセンブリーという。

例えば、ある DNA の塩基配列が ATGATCCTAGACCCTGAT であったとする。この塩基配列を増幅させて、複数のコピーを作成する。続いて、この塩基配列をランダムに切断して、高速シーケンサーでシーケンシングすると、CCTAGA、ATGATCC、CCTGAT、GACCC の 4 リードが出力されたとする。この 4 リードから、元の塩基配列を復元するには、各リードの先頭と後尾の文字列に着目し、あるリードの先頭が他のリードの後尾と重なるように並べ替えることで可能になる。つまり、次のような図において、各頂点(リード)を 1 回だけ通るパスを探し出せれば、元の塩基配列を復元できるようになる。

「各頂点を 1 回だけ通るパスを探す」問題は、ハミルトン閉路問題として知られる。ハミルトン閉路問題は、NP 困難であることが知られている。頂点(リード)の数が増えることで、問題を解くの膨大な計算リソースを必要とする。特に、高速シーケンサーは、一般的に数十万から数百万のリードを出力するために、この問題を解くのがますます困難となる。

これを解くために、ハミルトン閉路問題をオイラー閉路問題に置換させて解く方法が取られている(Pevzner et al., 2001, Compeau et al., 2011)。すなわち、すべての頂点(リード)を 1 回だけ通るパスを見つける代わりに、各経路を 1 回だけ通るパスを見つける問題に置換させて解く。ハミルトン閉路問題をオイラー閉路問題に置換させるために、まずリードの塩基配列をさらに長さ k の塩基配列(k-mer)に切断する。例えば、2-mer ならば次のようになる。次に、2-mer の塩基配列を頂点として、繋げていく。このように出たグラフは de Bruijn グラフとよぶ。このグラフにおいて、すべてのパスを 1 回だけ通るようなパス(オイラー閉路)を見つければ、元の塩基配列を復元できる。オイラー閉路を見つけるアルゴリズムは、NP 困難ではなく、高速で見つかるアルゴリズムも報告されている。

References

  • Compeau PE1, Pevzner PA, Tesler G. How to apply de Bruijn graphs to genome assembly. Nat Biotechnol. 2011, 29(11):987-91. DOI: 10.1038/nbt.2023 PMID: 22068540
  • Pevzner PA1, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci U S A. 2001, 98(17):9748-53. DOI: 10.1073/pnas.171285098 PMID: 11504945
  • hoxo_m. de Bruijn Graph を使った de novo アセンブリの発想がすごい件. 2010. ほくそ笑む