担当 : 山下 洋史
題目 : Metagenomics アセンブラ “MEGAHIT” の改良
概要：
ゲノム解析では,全ゲノム・ショットガン・シークエンシングという方法が用いられている．この手法では,断片化した DNA をシーケンサーを用いて読み取り，それらを組み合わせることでできるだけ長い DNA の塩基配列の断片を再現する de novo アセンブリと呼ばれる操作が行われる．多種の微生物を対象とするメタゲノミクスの de novo アセンブリを精度よく，かつ効率的に行うソフトウェア MEGAHIT [1]が開発された．MEGAHIT は，長さ k の塩基配列を節点とする de Bruijn グラフと呼ばれるグラフを用いてアセンブリを行う．
本発表では，MEGAHIT において de Bruijn グラフを表現するために用いられている Succinct de Bruijn Graph [2] というデータ構造を紹介し，卒業研究で行ったMEGAHITの改善について述べる．
参考文献 :
[1] Dinghua Li, Chi-Man Liu, Ruibang Luo, Kunihiko Sadakane and Tak-Wah Lam: MEGAHIT: An ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph. arXiv:1409.7208 [q-bio.GN], 2014.
[2] Alexander Bowe, Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya: Succinct de Bruijn Graphs. In Proceedings of The 12th International Workshop on Algorithms in Bioinformatics, LNCS 7534, pp. 225–235, 2012.
