ハッシュテーブル及び de Bruijn Graph の分割による、 ゲノム解析の

情報処理学会第 76 回全国大会
2ZD-8
ハッシュテーブル及び de Bruijn Graph の分割による、 ゲノム解析の消費メモリ量の低減 杉浦 典和† 石田 貴士† 秋山 泰† 関嶋 政和† †
東京工業大学大学院情報理工学研究科 1. はじめに 現在，ゲノムの解析には次世代シークエンサ
と呼ばれるゲノム読み取り装置が用いられてい
る．次世代シークエンサは，大量のゲノムを高
速かつ低価格に読み取ることができる一方，読
み取るゲノム断片配列の長さが数十から百数十
塩基しかないという欠点を持っている．このた
め，出力された短いゲノム断片配列をアセンブ
リすることによって，元の長いゲノム配列に再
構築しなければならない． シークエンサから得られるゲノム断片配列を
リードと呼び，このリードを他のゲノム配列を
参照すること無しに元の長いゲノム配列に再構
築することを de novo アセンブリという．また
アセンブリを行うツールをアセンブラと呼ぶ．
次世代シークエンサの登場以来，短いリードを
ア セ ン ブ リ す る た め ， Velvet[1] ， AllpathsLG[2]，SOAP denovo[3]など様々なショートリー
ド向けアセンブラが開発されてきた．これらの
de novo アセンブラは，ショートリードを効率的
にアセンブリするために de Bruijn Graph を利
用している．これによって次世代シークエンサ
が出力するような短いリードでも，おおよそ元
の長いゲノム配列にアセンブリすることが可能
になっている． しかしこれらのアセンブラはその消費メモリ
量が課題とされており，特にヒトゲノムのよう
に大規模なゲノムの de novo アセンブリにおい
ては，数テラバイトに及ぶ膨大な量のメモリが
必要となることが知られている[4]．そこで本研
究では，代表的なショートリード向けのアセン
ブラの 1 つであり，アセンブリ結果に一定の信
頼が得られている Velvet を改良し，Velvet のア
センブリ結果を維持したまま，少量のメモリし
か搭載していない 1 台の計算機でも大きなゲノ
ムをアセンブリできるように改良することを目
指す． Memory usage reduction of genome analysis by dividing
hash tables and de Bruijn Graphs
Norikazu Sugiura†, Takashi Ishida†, Yutaka Akiyama†,
Masakazu Sekijima†
2. ハ ッ シ ュ テ ー ブ ル 及 び de Bruijn Graph の分割手法 Velvet は 以 下 の 5 つ の ス テ ッ プ に 大 別 で き
る ． 1. ハ ッ シ ュ テ ー ブ ル を 用 い た ROADMAP 生 成 2. ROADMAPS を 用 い た PreGraph 生 成 3. K-mer 検 索 テ ー ブ ル を 用 い た Graph 生 成 4. TourBusAlgorithm 等 に よ る エ ラ ー 削 除 5. Paired-end 情 報 を 用 い た scaffold 生 成 本研究では特に消費メモリ量の大きいデータ
構造に着目し，これらを分割することで消費メ
モリ量の削減を行う．またハッシュテーブルと
PreGraph については，既にこれらを分割する手
法[4][5]が提案されているのでこれらを実装し，
ここでは Graph 生成過程以降の処理について分
割手法を提案する． まず Graph の分割手法について述べる．Graph
生成においては，まず PreGraph から全ノードを
読み込み，さらに各ノードから k-mer を生成し
k-mer 検索テーブルに格納する．次に入力リード
を一本ずつ読み込み，さらにリードからも k-mer
を生成し，この k-mer を k-mer 検索テーブルで
検索する．このとき，リード内の隣り合う k-mer
が別々のノードから生成されていた場合に，こ
れらのノードを結ぶエッジを生成する．このよ
うにして Graph を生成する．Graph 生成過程では
Graph 本体よりも，エッジ生成に用いる k-mer 検
索テーブルがメモリを消費している．本研究で
は，k-mer 検索テーブルを複数に分割してエッジ
生成過程を分散化することで，Graph 生成過程の
消費メモリ量を削減した． 次に Scaffold の生成過程について述べる．
Velvet は Graph を生成した後，Paired-end 情報
を用いてさらに Graph を単純化し Scaffold を生
成している．Scaffold 生成においては，Pairedend リードに対応するノードを瞬時に見分けるた
め，各リードから生成されるノードを保存する
Read-Node テーブルを生成しており，これがメモ
リを消費している．そこで Read-Node テーブル
を複数に分割し，Scaffold 生成過程の消費メモ
リ量を削減した． † Tokyo Institute of Technology, Tokyo, Japan
4-587
Copyright 2014 Information Processing Society of Japan.
All Rights Reserved.
情報処理学会第 76 回全国大会
3. 実験と考察 ここではハッシュテーブルと PreGraph，Graph
の分割する手法と非分割の場合の消費メモリ量
を比較する．ハッシュテーブルを分割する手法
の比較については，NCBI からダウンロードした
Saccharomyces bayanus の リ ー ド セ ッ ト （ SRA ID:SRR173086）を用い，パラメータは k=29 とし
て実験した．（図 1）また PreGraph と Graph を
分割する手法ついては，GAGE[6]からダウンロー
ドした Stapylococcus aureus のリードセットを
用い，k=35 で実験した．（図 2,3）また大規模
なゲノムを入力した場合の消費メモリ量を調べ
るため Human Choromosome 14 のリードセットを
用いて k=51 とし，各データ構造を 4 分割した場
合の消費メモリ量を測定した．（表 1）計算機は
東京工業大学が所有する TSUBAME 2.5 を使用し
て お り ， 使 用 し た 計 算 ノ ー ド は CPU が Intel Xeon 2.93GHz(6cores)×2 ， メ モ リ が 54GB
（ Human Chromosome 14 の実験は 96GB）である． 図 1 分割ハッシュテーブルの消費メモリ量 図 2 分割 PreGraph の消費メモリ量 図 3 分割 Graph の消費メモリ量 表 1 Human Chromosome 14 での消費メモリ量 図 1〜図 3 より，各データ構造の分割数を増や
すにつれて消費メモリ量が減少していることが
確認できる．またこれらの実験において，デー
タ構造を分割しても，アセンブリの結果が一致
することを確認している．よって各データ構造
の分割により，消費メモリ量の削減に成功した．
しかし，表 1 に示した Human Chromosome 14 の
実験では，出力結果に若干の差異が確認された．
Scaffold の生成までのグラフ構造は一致してい
たため，分割 Read-Node テーブルの生成過程で
結果に差異が生じてしまったものと考えられる． 4. 今後の課題 本研究では Velvet の消費メモリ量の削減を実
現したが，一部のリードセットでは出力結果の
不一致が確認されている．Velvet と同等の精度
を出せるよう，出力結果を完全に一致させたい．
また今回の提案手法は，本来 Velvet がサポート
している機能であるリファレンスシーケンスの
入力やロングリードのアセンブリには対応して
いない．今後はこれらについても改良し，幅広
い種類の入力に対応させることを目指す． 参考文献 [1] Daniel R.Zerbino et al: Velvet: Algorithms for de novo short read assembly using de Bruijn graphs, Genome Res.18: 821-829(2008) [2] Sante Gnerre,et al.: High-quality draft assemblies of mammalian genomes from massively parallel sequence data, Proc Natl Acad Sci USA, 108, 1513-1518.(2011) [3] Li, R. et al.:de novo assembly of human genomes with massively parallel short read sequencing, Genome Res, 20, 265-272. (2010) [4] 宇治橋善史,成瀬彰,宮本青,重元康,北館智：de novo assembler Velvet の メモリ使用量を削減す
る プ ロ セ ス 並 列 手 法 ,IPSJ SIG technical reports(2012) [5] 杉浦 典和,石田 貴士,秋山 泰,関嶋 政和: de Bruijn Graph の PreGraph の分割による Velvet
の改良,IPSJ SIG Technical Report(2012) [6] Salzberg SL, et al.: GAGE: A critical evaluation of genome assemblies and assembly algorithms.Genome Res(2011) 4-588
Copyright 2014 Information Processing Society of Japan.
All Rights Reserved.