Comments
Description
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