...

ハッシュテーブルの分割によるde novo アセンブリの改良

by user

on
Category: Documents
11

views

Report

Comments

Transcript

ハッシュテーブルの分割によるde novo アセンブリの改良
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
ハッシュテーブルの分割による de novo アセンブリの改良
杉浦 典和1
石田 貴士1
関嶋 政和1
秋山 泰1
概要:代表的な de novo アセンブラの一つである Velvet は,大規模なゲノムのアセンブリにおいて消費メ
モリ量の多さが課題とされている.本稿ではハッシュテーブルを分割することで,特に消費メモリ量の多
い前半の velveth の消費メモリを削減する手法を提案した.またハッシュテーブルを分割する手法として,
新たにリード分割法を提案した.リード分割法の提案により,従来より提案されている k-mer 値に応じた
分割法に比べ,少数計算機で実行する際の実行時間の削減に成功した.
キーワード:de novo アセンブリ,Velvet,分散処理,ハッシュテーブル,次世代シークエンサ
De novo sequence assembly based on divided hash tables
Sugiura Norikazu1
Ishida Takashi1
Sekijima Masakazu1
Akiyama Yutaka1
Abstract: Velvet is one of the most representative de novo assembler. However it has a problem that its
memory consumption is too large for large scale assembling. Here, we propose a method to decrease the
memory consumption of velveth which is the first half of Velvet and requires generally larger memory than
the remaining half part. We propose a novel hash dividing method by dividing reads. By using this method,
we have succeeded to decrease the elapsed time compared to the existing method, which divides a hash table
corresponding the k-mer value.
Keywords: de novo assembly,Velvet,Distributed processing,Hash table,Next Generation Sequencer
1. はじめに
をアセンブリするため,Velvet[1],ABySS[2],SSAKE[3],
Edena[4],Euler[5] など,様々なショートリード向けのア
現在,ゲノムの解析には次世代シークエンサと呼ばれる
センブラが開発されてきた.これによって,現在では次世
ハイスループットなゲノム読み取り装置が用いられている.
代シークエンサが出力するような短いゲノム断片配列で
このシークエンサは大量のゲノムを高速かつ低価格に読み
も,元の長いゲノム配列(コンティグ)にアセンブリする
取ることができる一方,読み取るゲノム断片配列の長さが
ことが可能になった.
数十から百数十塩基しかないという欠点を持っている.こ
しかしアセンブリには大きなメモリと実行時間を必要と
のため,次世代シークエンサが出力した短いゲノム断片配
することが知られており,特にヒトゲノムののように大規
列は,元の長いゲノム配列に再構築する必要が有る.
模なゲノムのアセンブリには,数テラバイトに及ぶ膨大な
短いゲノム断片配列を,他のゲノム配列を参照すること
量のメモリが必要と言われている [6].そこで本研究では,
無しに元の長いゲノム配列に再構築することを de novo ア
代表的なショートリード向けのアセンブラの 1 つである
センブリと言い,アセンブリを行うツールのことをアセン
Velvet に着目し,特にメモリ消費が著しい前半のハッシュ
ブラと呼ぶ.次世代シークエンサの登場以来,短いリード
テーブルを生成するステップである velveth を分散化する
ことで,少量のメモリしか搭載していない 1 台∼数台の計
1
東京工業大学 大学院情報理工学研究科
Graduate School of Information Science and Engineering,
Tokyo Institute of Technology, Meguro, Tokyo 152–8550,
Japan
c 2012 Information Processing Society of Japan
算機でも大きなゲノムを高速にアセンブリできるように改
良することを目指した.
1
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
velveth を分散化する手法は既にいくつも提案されてお
り,Joshi らは k-mer 値を剰余分割アルゴリズムによって
各計算ノードに割り振り,計算ノード間で MPI 通信を行
うことで velveth と同様の結果を得る手法を提案してい
る [7].しかしこの手法では,MPI の通信コストの大きさ
が課題となっている.また宇治橋らは k-mer から一意に決
まるハッシュ値を計算ノード数で割った剰余を求めるこ
とでハッシュテーブルを分割し,最後に各計算ノードが生
成した k-mer インデックステーブルをマージすることで,
MPI 通信を行わずに velveth と同様の結果を得る手法を提
案している [8].また ABySS では velveth の処理にとどま
らず,各計算ノードに分割したハッシュテーブルを用いて
最終的なコンティグをもとめる過程まで一貫して実装して
いる.しかしこれらの手法のように剰余分割によってハッ
シュテーブルを分割する手法では,分割した個々のハッ
図 1 ハッシュテーブルのアクセス
シュテーブルのサイズのばらつきが大きいという問題を抱
Fig. 1 How to access a hash table
えている.
表 1 4 種のデータセット
本研究ではまず始めに,Velvet がその前半部分である
Table 1 4 datasets
velveth でメモリを多く消費することを示し,ABySS 等で
既に行われた k-mer 値に応じたハッシュテーブルの分割
データセット 1
データセット 2
手法を velveth に実装する(k-mer 値分割法)
.次に新たな
生物種
酵母
酵母
リード本数
33,377,822
28,889,948
ハッシュテーブルの分割法として,入力リードセットの分
リード長
51bp
114bp
割に基づくハッシュテーブルの分割法(リード分割法)を
総塩基数
1.7Gbp
3.3Gbp
提案し,各ハッシュテーブルの消費メモリの分散を低下さ
シークエンサ
Illumina G.A. II
Illumina G. A. II
せることを実現し,また少数計算機使用時の実行時間の削
SRA ID
SRR173084
SRR173086
データセット 3
データセット 4
生物種
出芽酵母
マラリヤ原虫
リード本数
25,306,308
36,505,692
リード長
40bp
76bp
総塩基数
1Gbp
2.8Gbp
シークエンサ
Illumina G.A. II
Illumina G.A. II
SRA ID
SRR066206
ERR027133
減にも成功したことを示す.
2. Velvet の構成とメモリ消費
2.1 Velvet の構成
Velvet は二つの実行ファイルから構成されており,一つ
目は velveth,二つ目は velvetg と呼ばれている.velveth
はハッシュテーブルを利用することで,リードのオーバー
ラップの情報を記録した「Roadmap」というファイルを
作成し,velveg は Roadmap に書かれた情報を元にして de
2.2 Velvet のメモリ消費
ここでは velveth と velvetg それぞれの消費メモリ量を,
Bruijn Graph[9] を作成しアセンブリを行う.velveth は以
4 種のデータセットに対し,パラメータ k の値を変えながら
下のステップに従い,リードのオーバーラップの情報を
調べる.ここでは NCBI の Sequence Read Archive(SRA)
Roadmap に記録している(図 1).
のウェブサイト [10] からダウンロードした 4 つのリード長
ステップ 1:リードを順番に読み込む
の異なるデータセットを利用した(表 1).また実験は同
ステップ 2:リードから k-mer を順番に取り出し,その
じ条件で 3 回ずつ行い,その平均値を求めた.
k-mer をハッシュテーブルに探しに行く.k-mer が見
その結果,消費メモリ量は表 2 のようになった.またそ
つからなかった場合はステップ 3 へ,見つかった場合
の k の値を利用した際に意味が有るアセンブリが行えたか
はステップ 4 へ進む.
否かを判断するため,n50 値 [11] も記した.この表より,
ステップ 3:その k-mer を生成したリードの ID と,その
リード中での出現箇所をハッシュテーブルに記録する.
n50 値が最も高くなるような k の値について着目すると,
velveth と velvetg はよく似た消費メモリ量となっている.
ステップ 4:ハッシュテーブルから,その k-mer を生成し
このことから,今回利用したデータセットについては一概
たリードの ID とそのリード中での出現箇所を取り出
に velveth と velvetg のどちらか一方がメモリを多く消費
し,Roadmap に記録する.
するとは断言できず,入力するデータセットに依存するこ
とがわかる.
c 2012 Information Processing Society of Japan
2
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
表 2 velveth と velvetg の消費メモリ量(MB)
装では入力されたリードセットの分割を行っていなかった
Table 2 The memory consumption of
ため,入力されたリードセットを保存するための主記憶が
velveth and velvetg (MB)
データセット 1
必要だった.本研究では入力するリードセットをまとめて
読み込まず,少しずつ読み込んでは解放するように実装し
データセット 2
k
velveth
velvetg
n50
velveth
velvetg
n50
23
5,159
10,844
9,882
9,610
36,894
8,049
29
5,159
6,008
30,370
10,699
20,407
16,250
39
5,167
5,100
27,408
11,238
8,452
21,213
49
-
-
-
11,377
7,150
22,131
57
-
-
-
10,540
7,058
33,043
k
velveth
velvetg
n50
velveth
velvetg
n50
23
2,745
2,465
17,973
6,942
-
-
29
2,745
2,353
12,186
7,626
-
-
35
2,745
2,614
2,208
-
-
-
39
-
-
-
8,832
6,852
1,541
49
-
-
-
8,224
6,852
2,550
57
-
-
-
7,035
6,963
3,012
データセット 3
たため,膨大なサイズのリードセットが入力されても消費
メモリを抑えられるように実装した.
データセット 4
しかし,次世代シークエンサの性能は日進月歩で向上し
ており,100bp を超える長さの paired end リードを出力
する次世代シークエンサも登場している [12].そして今後
図 2 k-mer 値によるハッシュテーブルの分割
は今日よりもさらに長いリードを出力するシークエンサが
Fig. 2 Dividing a hash table by a k-mer value
登場することが予想される.しかし,リードの長さやカバ
レッジにより最適な k の値は異なることが知られており,
Velvet の場合はリード長が長くなるに従い最適な k 値も増
3.1 sub Roadmap のマージ
加することが知られている [1].よって今後はリード長が長
次に,各計算ノードで生成された sub Roadmap をマー
くなるに従い最適な k の値も大きくなっていくことが予想
ジする流れについて述べる.sub Roadmap は以下の手順
される.そしてそれに伴い k-mer を格納するハッシュテー
でマージされる.
ブルのサイズも増加し,velveth の消費メモリ量も増加する
まず存在する全ての sub Roadmap-i を開く.i は計算
と考えられる.このことはヒトなどの大きなゲノムのアセ
ノード番号である.これらの sub Roadmap-i から特定の
ンブリにおいて大きな障害となり得る重大な問題である.
リード m についての重なり合いの情報を取り出す.全て
よって本研究では,Velvet のハッシュテーブルを分割し,
の sub Roadmap-i からこの情報を取り出すことにより,
ハッシュテーブル作成ステージである velveth を分散化を
リード m に含まれる各 k-mer と一致する k-mer の情報を
目指す.
全て集めることができる.この情報を整理すると重なり
3. 従来手法の改良
ここでは宇治橋らによって提案されている手法の改良を
行い,また彼らの論文では触れられていなかった k-mer イ
ンデックス部分テーブル(本研究では sub Roadmap と呼
合うリードの情報に再解釈することができる.こうして
sub Roadmap に記録されていた一致する k-mer の情報を,
重なり合うリードの情報に変換し Roadmap に記録して
いく.
例えば sub Roadmap-1 と sub Roadmap-2 にそれぞれ
ぶ)のマージ処理について言及する.宇治橋らの手法では,
表 3,表 4 のような記述があった場合,これらの表からは
k-mer から一意に決まる値の剰余分割によってハッシュ
以下の 3 つの情報が読み取れる
テーブルの分割を行う.ただし,彼らは k-mer 値から一意
に決まるハッシュ値を計算ノード数で割っているのに対し,
本研究では ABySS と同様の手法で,k-mer とその相補鎖
の排他的論理和の値を計算ノード数で割った剰余分割を求
めた.各計算ノードは一つずつ分割されたハッシュテーブ
ルを保持し,それぞれの計算ノードの上で sub Roadmap
の作成を行う.最後にこれらの sub Roadmap をマージし,
最終的な Roadmap を得る(図 2)
.ただし,宇治橋らの実
c 2012 Information Processing Society of Japan
• リード 10 の 0 番目の k-mer とリード 5 の 3 番面の
k-mer が一致する.
• リード 10 の 2 番目の k-mer とリード 5 の 5 番目の
k-mer が一致する.
• リード 10 の 1 番目の k-mer とリード 5 の 4 番目の
k-mer が一致する.
これらの 3 つの情報を足し合わせると,リード 10 と 0
番目から 2 番目の k-mer と,リード 5 の 3 番目から 5 番目
3
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
表 3 sub Roadmap 1 の ROADMAP 10
Table 3 ROADMAP 10 of sub Roadmap 1
ROADMAP 10
5 0 3 5 2 5
表 4 sub Roadmap 2 の ROADMAP 10
Table 4 ROADMAP 10 of sub Roadmap 2
ROADMAP 10
5 1 4 表 5 Roadmap の ROADMAP 10
Table 5 ROADMAP 10 of Roadmap
図 3 リード分割によるハッシュテーブルの分割
Fig. 3 Dividing a hash table by divided reads sets
ROADMAP 10
5 0 3 6 の k-mer が重なっていることが解る.よって Roadmap は
表 5 のように記述する.
4. リードの分割によるハッシュテーブルの分
割法の提案
k-mer の値に応じてハッシュテーブルを分割する手法は
従来より提案されているが,この手法ではハッシュテーブ
ルの分割数に対し必ずしもリニアに消費メモリ量が減少す
るとは限らない.例として計算ノード数が n のとき,k-mer
図 4 sub Roadmap k の構造
を n で割った剰余番目の計算ノードにその k-mer を割り振
Fig. 4 Structure of sub Roadmap k
る手法を考える.このときもし入力されたデータセットか
ら生成した k-mer が,n で割り切れる k-mer ばかりだった
して行く.また一致する k-mer が既にハッシュテーブル
ならば,ほとんどの k-mer が n 番目の計算ノードのハッ
内に存在したときはそのリード情報を「sub Roadmap i」
シュテーブルに集中して格納されてしまうことになる.こ
に記録する.最後にこれらの sub Roadmap i をマージし
れでは 1 計算ノードあたりのピークメモリを減らすことは
Roadmap を生成する(図 3).
できない.
そこで新たなハッシュテーブルの分割手法として,リード
4.2 sub Roadmap の作成
を分割することによってハッシュテーブルを分割する手法
各計算ノードは割り振られた分割リードセットからハッ
を提案する.またこの手法を velveth に適用し,Roadmap
シュテーブルを生成する.計算ノード数が n のとき,先
を分散処理で生成する手法を提案する.
に述べたように計算ノード k は分割リードセット k ∼n を
割り振られている.このとき,ハッシュテーブルに書き
4.1 Roadmap 作成までの流れ
込む権限は分割リードセット k のみが持っており.分割
この手法でもハッシュテーブルは各計算ノードに一つず
リードセット k + 1∼n はその権限を持っていない.よって
つ割り振られる.また入力されたリードセットも計算ノー
k + 1∼n はハッシュテーブルを参照し,一致する k-mer の
ドの数に分割して考える.これらの分割リードセットは,
情報を sub Roadmap に記録はするものの,ハッシュテー
ある規則に従って各計算ノードに割り振られる.計算ノー
ブルに k-mer の情報を記録することはできない.この手順
ド数が n の場合,1 番目の計算ノードはリードセット 1∼
によって生成された sub Roadmap k は,図 4 のような構
n を,2 番目の計算ノードはリードセット 2∼n を,k 番目
造になっている.
の計算ノードはリードセット k ∼n を割り振られる.
各計算ノードは与えられた分割リードセットから k-mer
を生成し,それらの k-mer を順にハッシュテーブルに格納
c 2012 Information Processing Society of Japan
4.3 sub Roadmap のマージ
次に,これらの sub Roadmap をマージすることで最終
4
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
表 6 sub Roadmap 1 の ROADMAP 195
Table 6 ROADMAP 195 of sub Roadmap 1
ROADMAP 195
43 2 0 4 表 7 sub Roadmap 2 の ROADMAP 195
Table 7 ROADMAP 195 of sub Roadmap 2
ROADMAP 195
88 0 0 5 表 8 Roadmap の ROADMAP 195
図 5 重なり合うリード情報の選択
Table 8 ROADMAP 195 of Roadmap
Fig. 5 How to select the overlapping reads
ROADMAP 195
88 0 0 2 43 0 0 4 5. 実験
ここでは k-mer 値によるハッシュテーブルの分割を利用
して分散化する手法(k-mer 値分割法)と,リードの分割
的な Roadmap を得る.ただしこのとき,重なるリードの
によるハッシュテーブルの分割を利用して分散化する手法
選択に注意しなければならない.例えば sub Roadmap 1
(リード分割法)について,それぞれの消費メモリ量と実行
と sub Roadmap 2 にそれぞれ表 6,表 7 のような記述が
時間を,オリジナルの velveth と比較する.
あった場合,以下の二つの情報がわかる.
• リード 195 の 2 番目の k-mer からリード 43 と k-mer4
本分重なる.
• リード 195 の 0 番目の k-mer からリード 88 と k-mer5
本分重なる.
この情報から,リード 43 とリード 88 は一致する k-mer
を持っていることがわかる.しかしハッシュテーブルを分
5.1 実験環境,測定方法
実験には 2 章で使用したデータセット 2 を使用した.ま
た k 値は 29 とした.使用した計算機は,東京工業大学が所
有する計算機,TSUBAME 2.0 である.使用した計算ノー
ドのスペックは CPU が Intel Xeon 2.93 GHz (6 cores) ×
2,メモリが 54GB である.
割せずに Roadmap を生成した場合,この情報は得られる
消費メモリ量の測定には,プログラム内部で使用した
はずのない情報である.なぜならハッシュテーブルには若
malloc 関数によって確保したメモリサイズの合計を用い,
いリードから取り出された k-mer から順に格納されて行く
実行時間の測定には gettimeofday 関数を使用した.これ
ので,リード 43 に含まれる k-mer を格納した後にリード
らの値については,実験を行った TSUBAME 2.0 のバッ
88 に含まれる k-mer を格納する.書き込もうとした k-mer
チシステム(PBSpro)が記録したピークメモリや実行時
が既にハッシュテーブルに存在したときは,上書きされ
間と比較しほぼ同一の値になることを確認している.
ない.よってリード 88 とリード 43 の一致する k-mer は,
リード 43 の k-mer として格納されていることがわかる.
よってハッシュテーブルを分割していなければ,ハッ
5.2 消費メモリ量
sub Roadmap 生 成 に 必 要 な 消 費 メ モ リ 量 と
シュテーブルからは以下の情報が得られ,Roadmap には
sub Roadmap マ ー ジ に 必 要 な 消 費 メ モ リ 量 を ,表 9,
表 8 のような記述が存在しているはずである.
表 10 に示す.この表より,k-mer 値分割法においても
• リード 195 の 0 番目の k-mer からリード 88 と k-mer2
本分重なる.
• リード 195 の 2 番目の k-mer からリード 43 と k-mer4
本分重なる.
sub Roadmap をマージするときは,このことを考慮して
リード分割法においても,sub Roadmap 生成に必要な消
費メモリ量が常に大きくなっていることがわかる.よって
今後は sub Roadmap 生成に必要な消費メモリ量について,
k-mer 値分割法とリード分割法をを比較することにする.
次に分散した計算ノード毎の消費メモリ量を調べるため,
マージする必要がある.実装では,二本のリードが重なり
k-mer 値分割法,リード分割法のそれぞれについて,計算
合っているとき,図 5 のようにリード ID の若い方のリー
ノード数が 4,8,16,32,64,128 の 6 通りの場合の消費
ドを選択して記録する.
メモリ量を調べた.またそれぞれのノードの消費メモリ量
の最大値と平均値,標準偏差を求めた.その結果,全ての
c 2012 Information Processing Society of Japan
5
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
表 9 sub Roadmap 生成の消費メモリ量(MB)
Table 9 The memory consumption to
make sub Roadmap(MB)
k-mer 値分割法
velveth
リード分割法
10,699
4 分割
2,686
2,980
8 分割
1,502
1,796
16 分割
911
1,166
表 10 sub Roadmap マージの消費メモリ量(MB)
Table 10 The memory consumption to
merge sub Roadmap (MB)
k-mer 値分割法
リード分割法
なし
velveth
4 分割
516
1,111
8 分割
262
561
16 分割
135
285
表 11 ハッシュテーブルを 8 分割したときの消費メモリ量(MB)
Table 11 The memory consumption (MB)
when dividing a hash table into 8
k-mer 値分割法
リード分割法
ノード 1
1,255
1,624
ノード 2
1,196
1,666
ノード 3
1,230
1,712
ノード 4
1,322
ノード 5
図 6 k-mer 値分割法とリード分割法の消費メモリ量の比較
Fig. 6 Comparison of the memory consumption between
k-mer division method and reads division method
表 12 ハッシュテーブルを 8 分割したときの実行時間(秒)
Table 12 The elapsed time (sec.) when
dividng a hash table into 8
k-mer 値分割法
リード分割法
ノード 1
645
980
ノード 2
631
863
1,775
ノード 3
634
742
1,268
1,796
ノード 4
640
627
ノード 6
1,326
1,742
ノード 5
640
503
ノード 7
1,247
1,687
ノード 6
639
375
ノード 8
1,502
1,641
ノード 7
633
251
最大値
1,502
1,796
ノード 8
651
128
平均値
1,293.3
1,705.4
最大値
651
980
標準偏差
88.9
58.2
平均値
639.1
558.6
合計値
5,113
4,469
分割数において同様の傾向が見られたので,ここでは計算
ノード数 8 で実験した場合について考察する(表 11).
表 11 より,最大消費メモリ量を持つ計算ノードの消費
計算ノードの消費メモリ量の平均値と最大値の値が近いの
は,常にリード分割法となっていることがわかる.
メモリ量についても,各計算ノードの消費メモリ量の平均
値についても,k-mer 値分割法の方が小さいことがわかる.
5.3 実行時間
しかしリード分割法の方が各ノードにおける消費メモリ量
分散した計算ノード毎の実行時間を調べるため,k-mer
の標準偏差が小さいので,各ノード毎の消費メモリ量のば
値分割法,リード分割法のそれぞれについて,計算ノード
らつきが大きいという k-mer 値分割法の問題点を,リード
数が 4,8,16,32,64,128 の 6 通りの場合について実験を
分割法は解決できたと言える.しかし,各ノード毎の消費
行った.また,それぞれの計算ノードの実行時間の最大値
メモリ量が大きいため,結果としてピークメモリはリード
と平均値,また前ノードの合計値を求めた.その結果,全
分割法の方が大きくなってしまっている.
ての分割数において,同様の傾向が見られたので,ここで
また図 6 は,分散した計算ノードの中で最も大きなメモ
は計算ノード数 8 で実験した場合(表 12)について示す.
リを消費する計算ノードの消費メモリ量(最大消費メモリ
表 12 より,最も実行時間の長い計算ノードの実行時間
量)と,各計算ノードの消費メモリ量の平均値を,4∼128
(以後,最大実行時間と呼ぶ)は,常にリード分割法の方
のそれぞれの分割数についてまとめるたものである.この
が大きい.よって,各計算ノードを同時に実行させるなら
図より,どのノード数で分割しても k-mer 分割法の方が最
ば,k-mer 値分割法の方が短い実行時間で終了できる.し
大消費メモリ量が小さくなっていることがわかる.また各
かし,各計算ノードの平均値や,全ての計算ノードの合計
c 2012 Information Processing Society of Japan
6
Vol.2012-BIO-29 No.25
2012/6/29
情報処理学会研究報告
IPSJ SIG Technical Report
なった.
7. 今後の課題
本研究では sub Roadmap の生成ステップを中心に消
費メモリ量や実行時間の比較を行ったが,sub Roadmap
のマージステップの実行時間は無視できない大きさであ
る.よって sub Roadmap のマージステップを分散化し,
sub Roadmap の生成にかかる時間と同等かそれ以下の実
行時間でマージできるようにすることが望ましい.
また本研究では velveth の分散化についてのみ考察を
行ってきたが,velvetg も大きなメモリを消費することが知
られている.今後は velvetg も分散化し,Velvet 全体を分
散化することが必要である.
図 7 k-mer 値分割法とリード分割法の実行時間の比較
Fig. 7 Comparison of the elapsed time between k-mer
division method and reads division method
値はリード分割法の方が小さい.よって,複数の計算ノー
参考文献
[1]
[2]
ドで一斉に実行するのではなく,一つの計算機上で順番に
実行して行く場合には,リード分割法の方が短い実行時間
で終了できると言える.
[3]
また図 7 は,分散した全ての計算ノードの合計実行時間
を,4∼128 のそれぞれの分割数についてまとめたものであ
る.この図より,全計算ノードの合計実行時間は計算ノー
[4]
ド数が増えるにつれ急速に増加する傾向が有り,常にリー
ド分割法の方が小さいことがわかる.
6. 結論
リード分割法の提案により,k-mer 値分割法より各計算
[5]
[6]
ノードの消費メモリ量の分散を減らすことに成功した.し
かし,各計算ノードあたりの消費メモリ量が k-mer 値分
割法の方が小さかったたため,結果としてピークメモリは
[7]
k-mer 値分割法の方が低くなった
また実行時間については,k-mer 値分割法の方が各計算
ノードの実行時間のばらつきが小さいので,分割したハッ
[8]
シュテーブルを複数の計算ノードで同時に実行する場合は
k-mer 値分割法の方が実行時間が短い.しかし各計算ノー
ドの合計実行時間はリード分割法の方が短いので,1 台∼
[9]
数台の計算ノードで順番にハッシュテーブルを生成して行
くときは,リード分割法の方が実行時間が短くなることが
[10]
わかった.
本研究で実装した二種類の手法は,どちらも Velvet が生
成する中間ファイルである Roadmap を生成するので,こ
のファイルをそのまま Velvet のグラフ作成実行ファイル
[11]
[12]
Daniel R. Zerbino and Ewan Birney: Velvet: Algorithms
for de novo short read assembly using de Bruijn graphs,
Genome Res. 18: 821-829 ,(2008)
Jared T. Simpson, Kim Wong, Shaun D. Jackman,
Jacqueline E. Schein, Steven J.M. Jones, and Inanxc
Birol, et al.: ABySS: A parallel assembler for short read
sequence data, Genome Res. 19: 1117-1123,(2009)
Rene’ L. Warren, Granger G. Sutton, Steven J. M. Jones
and Robert A. Holt: Assembling millions of short DNA
sequences using SSAKE, Bioinformatics 23 (4): 500501. (2007)
David Hernandez, Patrice Francois, Laurent Farinelli,
et al.: De novo bacterial genome sequencing: Millions
of very short reads assembled on a desktop computer,
Genome Res. 18(5): 802-809. 2008 May
Mark J. Chaisson and Pavel A. Pevzner: Short read fragment assembly of bacterial genomes, Genome Res. 18(2):
324-330. 2008 February
Schatz, Michael: Assembly of Large Genomes using
Cloud Computing,
http://schatzlab.cshl.edu/presentations/2010-0723.Illumina.pdf, (2010)
Nitin Joshi, Shashank Shekhar Srivastava, M. Milner
Kumar, Jojumon Kavalan, Shrirang K. Karandikar and
Arundhati Saraph: Parallelization of Velvet,“a de novo
genome sequence assembler”, HiPC. (2011)
宇治橋善史,成瀬彰,宮本青,重元康,北館智:de novo
assembler Velvet の メモリ使用量を削減するプロセス並
列手法, IPSJ SIG technical reports 2012-BIO-28(9), 1-6,
2012-03-21,(2012)
Pevzner, P.A., Tang, H. and Waternam, M.S.: An Eulerian path approach to DNA fragment assembly, Proc.
Natl Acad. Sci. USA, Vol.14, pp.9748-9753.
Sequence Read Archive(SRA)
http://www.ncbi.nlm.nih.gov/sra/
Lander, E.S., et al.: Initial sequencing and analysis of
the human genome, Nature, 409, 860-921. (2001)
illumina
http://www.illumina.com/
である velvetg の入力として利用できる.また,どちらの
手法も計算ノード間の通信を行っていないので,必ずしも
複数台の計算機を用意する必要は無く,搭載メモリの小さ
い 1 台の計算機でも,大規模なゲノムを扱うことが可能と
c 2012 Information Processing Society of Japan
7
Fly UP