ゲノム解析における並列処理の事例紹介 北陸先端科学技術大学院大学 知識科学研究科 佐藤賢二

ゲノムデータ 主に分子生物学の実験の結果得られるデータ。 世界各国で集積・配付されている。 核酸配列情報 GATC… タンパク質配列情報　　SER ALA PRO … タンパク質立体構造情報 遺伝病などの疾病に関する情報 文献情報 …

ゲノム情報処理で並列処理が必要な理由 実験技術の進歩によりデータが加速度的に増え続ける 例）キーワード検索やホモロジー検索の並列処理 Combinatorial Computation が要求されることが多い 例）モデル生物の全ゲノム配列が続々と決定された ことにより、ゲノム全体を比較して生物の進化を 調べる Comparative Genomics が活発化 例）相関ルール発見などのデータマイニング手法を 用いてゲノムに関する知識発見を行いたい タンパク質は巨大分子（数万の原子の間の力学） 例）分子動力学（どっちかというとベクトル化？）

指数的に増え続けるゲノムデータ 実験技術の進歩とともに、 データの産出速度が加速

ゲノムデータの例（GenBankのエントリ） LOCUS EBOMAY 157 bp ss-RNA VRL 15-SEP-1990 DEFINITION Ebola virus 3' proximal protein gene, 5' end. ACCESSION M33062 NID g323684 KEYWORDS . SOURCE Ebola virus (strain MAY; Zaire 1976) RNA. ORGANISM Ebola virus Viruses; ssRNA negative-strand viruses; Mononegavirales; Filoviridae; Filovirus. REFERENCE 1 (bases 1 to 157) AUTHORS Kiley,M.P., Wilusz,J., McCormick,J.B. and Keene,J.D. TITLE Conservation of the 3' terminal nucleotide sequences of Ebola and Marburg virus JOURNAL Virology 149, 251-254 (1986) MEDLINE 86124724 FEATURES Location/Qualifiers source 1..157 /organism="Ebola virus" /db_xref="taxon:11268" CDS 53..>157 /note="3'proximal protein" /codon_start=1 /db_xref="PID:g323685" /translation="MRKINNFLSLKFDDRNLKLKLLICNHTVDSEPHTS" BASE COUNT 56 a 22 c 31 g 48 t ORIGIN 1 gggcacacaa aaagaaagaa gaatttttag gatcttttgt gtgcgaataa ctatgaggaa 61 gattaataat ttcctctcat tgaaatttga tgatcggaat ttgaaattga aattgttgat 121 ctgtaatcac accgttgatt cagagccaca cacaagt //

ゲノムデータの量（エントリ数） 核酸配列 （遺伝子） アミノ酸配列 （タンパク質） タンパク質立体構造 アミノ酸配列 アミノ酸配列の Date Database Release #Entries #Residues ------ ------------- -------------------- ---------- ------------ 98/9/22 genbank 108.0 (Aug 98) 2,532,359 1,797,137,713 98/10/27 genbank-upd 108.0+/10-28 (Oct 98) 428,496 439,645,601 98/8/25 embl 55 (Jun 98) 2,131,533 1,434,776,497 98/10/24 embl-upd 55+/10-24 (Oct 98) 646,766 635,494,813 98/8/25 swissprot 36.0 (Jul 98) 74,019 26,840,295 98/10/20 swissprot-upd 36.0+/10-20 (Oct 98) 9,429 3,825,820 98/8/25 pir 57.0 (Jun 98) 109,075 34,838,376 98/9/18 prf 98-09 (Sep 98) 108,435 39,113,650 98/8/25 pdb 84.0 (Apr 98) 7,533 2,644,523 98/9/4 pdb-upd 84.0+/09-04 (Sep 98) 560 208,475 98/8/25 pdbstr 84.0 (Apr 98) 12,420 2,617,704 98/9/4 pdbstr-upd 84.0+/09-04 (Sep 98) 926 204,113 98/8/25 epd 50.0 (Apr 97) 1,308 784,800 98/8/25 transfac 3.4 (May 98) 7,321 98/8/25 prosite 15.0 (Jul 98) 1,352 98/8/25 prosdoc 15.0 (Jul 98) 1,014 98/8/27 blocks 10.0 (Feb 98) 3,845 98/8/25 prints 18.0 (May 98) 865 98/8/25 prodom 34.2 (Nov 97) 53,597 6,756,724 98/8/25 pmd 96-05 (May 96) 7,078 98/9/8 aaindex 3.0 (Sep 98) 500 98/9/9 litdb 24-16 (Aug 20) 298,878 98/10/27 omim MIM10+/10-27 (Oct 98) 10,116 98/10/28 genes 8.0+/10-28 (Oct 98) 76,891 70,793,382 98/10/27 ligand 18.0+/10-26 (Oct 98) 9,291 98/10/28 pathway 8.0+/10-28 (Oct 98) 2,092 98/8/27 brite 0.5 (May 98) 87 98/10/28 linkdb 98-10-28 (Oct 98) 6,269,418 核酸配列 （遺伝子） アミノ酸配列 （タンパク質） タンパク質立体構造 アミノ酸配列 プロモータ配列 転写因子 アミノ酸配列の モチーフ（パタ ーン辞書） 変異タンパク（ミュータント） アミノ酸の各種指標 文献データ（PRFから生成） 遺伝病 遺伝子百科 事典（KEGG） 上記データ全ての参照関係 -upd がついているものは、毎日更新される追加分。その他は定期／不定期に更新。

ゲノムネット（GenomeNet) JAISTのミラーサーバ 京大化研 スパコンラボ（SCL) 東大医科研 ヒトゲノム解析センター（HGC)

京大（SCL）のシステム構成

東大（HGC）のシステム構成 日立SR2201 256+16PE SGI CRAY Origin2000 256PE Sun StarFire 64PE

JAISTのシステム構成 Sun Ultra Enterprise 3000 (4PE, 512MB, 270GB) オートマウントに組み込んでいるので、学内の マシンならどこでもデータを参照できる（Solarisと IRIXでは検索／解析プログラムも実行可能） 最近の悩みは 2GB over のファイルの扱い

ディスク消費量 現在の消費量は約１３７GB Filesystem kbytes used avail capacity Mounted on /dev/dsk/c1t3d3s7 8316189 6435222 1872651 78% /bio /dev/md/dsk/d30 43384774 14636512 28314415 35% /export/db100 /dev/md/dsk/d31 43384774 24394785 18556142 57% /export/db101 /dev/md/dsk/d32 43384774 20385732 22565195 48% /export/db102 /dev/md/dsk/d33 17409222 13157024 4078106 77% /export/db103 /dev/md/dsk/d34 43384774 33867103 9083824 79% /export/db104 /dev/md/dsk/d35 43384774 30955945 11994982 73% /export/db105 現在の消費量は約１３７GB

データ更新の様子 JAIST EBI NCBI HGC NIG SCL … DB更新 必要な データ を取得 東京と京都で互いに データ交換 国内外から最新データを 取得（一次ミラーリング） HGC SCL

ゲノムネットのサービス ftpミラーリング（最新のゲノムデータのコピーを持つ） DBGET（キーワード検索／エントリ取得） LinkDB（関連したエントリを辿る） ホモロジーサーチ（類似した配列の検索） 他の配列解析ツール（PSORT etc.） 日本独自のゲノムデータを公開（BSORF, MBGD, etc.） 遺伝子百科事典（KEGG )

ゲノムネットのWWWサーバ http://www.genome.ad.jp/

DBGET

DBGETを使ってGenBankを検索

検索結果のリスト

リストに挙がっているエントリを表示

LinkDB

LinkDB

ホモロジー検索（BLAST)

BLASTの実行結果

ゲノムネットにおける主な並列化 まず、SCLのStarFireでWeb経由のアクセスを受け付ける。 DBGETによるキーワード検索のうち、探索空間が非常に大きい もの（GenBankやEMBLなどの核酸配列データベース）はSCL のOriginに検索要求を投げ、４０並列×N でさばく。他はSCLの StarFireでそのまま処理する（こちらは１２並列×N）。 ホモロジー検索のうち、FASTAについてはHGCのSR2201に 検索要求を投げ、１６～３２並列×N でさばく。 BLASTについてはHGCのOriginに投げ、３２並列×Nでさばく。 サービスは他にも色々あるが、状況に応じて要求を投げるマシン を適宜変更しながら対応している。

並列化の手法とキャッシュ FASTAとBLASTはマルチスレッドで並列化。Solaris では POSIX の pthread と Sun 独自の thread を選択できるが、パフォーマンス上の 違いはあまり見られない。 HGCのSR2201でさばいている並列化FASTAは特注プログラム。 DBGETはコンパイル時の設定によりマルチプロセスで並列化。 StarFire（Solaris）では検索に使ったファイルがメモリにキャッシュされ るので、DBGETやFASTAやBLASTが２回目からは速くなる。キャッ シュされるファイルのサイズは大きいもので５００MB以上。多分Origin （IRIX）も同様の機構で速くなる。SR2201（HI-UX/MPP）は少し違う 機構だが、やはり主記憶常駐化により２回目からFASTAが速くなる。

JAIST内の各種のマシンで DBGET(8プロセス版）を使ってみる db1(E3000) db2(E3000) sf1(StarFire) ks18e0o00(Octane) 4PE 4PE 32PE 2PE メモリ 512MB/10MB 512MB/401MB 4GB/1.76GB 128MB/- の状態 １回目 35.3 sec 33.8 sec 60.6 sec 26.45 sec の検索 メモリ 512MB/10MB 512MB/92MB 4GB/1.46GB 128MB/- ２～１１ 24.95 sec(ave.) 5.23 sec(ave.) 6.36 sec(ave.) 27.297 sec(ave.) 回目の 検索 メモリ 512MB/10MB 512MB/91MB 4GB/1.46GB 128MB/-

傾向と対策 DGBETとFASTAとBLASTを同じマシンでサービスする場合、 とにかくメモリが数GB空いてないと遅くて駄目。できればデータ ベース更新用のマシンと検索用のマシンを分けた方が良い。 → JAISTのサーバ（db1）では近々4GBに増設予定 核酸配列が検索対象の場合、３２並列前後で台数効果が下が り始めるので、多数の検索要求をさばく場合は１６並列×Nとか ３２並列×Nくらいの方が、多分全体のスループットが上がる。 アミノ酸配列が検索対象の場合、核酸に比べると探索空間が ８分の１くらいなので、空きメモリも少なくてよい。当然計算量も 少ないので、４並列×Nくらいが適当。

データマイニング（１） ー 相関ルール発見 ー ・IBMのAgrawalらが1993年に提案。商品の販売記録を分 析し、商品間の相関関係を把握するために使用された。 ・１回の商品購入で一緒に買われる頻度が高い商品集 　合を検索し、ルール化する。 ・ルールの価値はサポートおよび確信度という２つの 　パラメータで定量的に評価される。 ・サポートがある値以下の組合せは計算途中で捨てる。 　同様に確信度がある値以下の相関ルールは生成しない。 ２段階処理

コンビニエンスストアの例 パン, バター => ミルク アイテム 顧客の購買 データ サポート= 2 確信度= 66.6% 相関ルール発見 （Apriori） 最小サポート= 1 最小確信度= 60% パン, バター => ミルク サポート= 2 確信度= 66.6%

相関ルール発見は計算が爆発しやすい 同時に買われる頻度が高い商品集合を検索する段階（第１ステップ）は 基本的に商品集合の全てのサブセットについて頻度計算を行うので、 Combinatorialな計算になる。無駄な計算を省いたAprioriアルゴリズム でもかなりの計算量になる。 第２ステップでルール化する部分では、しきい値が低いと大量のルール が生じるため、これも時間がかかる。 東大の喜連川研究室では、第１ステップの頻度計算を各候補サブセット をPEに割り付けて並列計算を行うHPAアルゴリズムを開発している。 １００ノードのPCクラスタで測定した結果、かなりリニアに台数効果が出て いる（詳しくは情報処理学会誌１１月号を参照）。

データマイニング（２） ー 論理積ルール ー 東大医科研の森下・中谷らは、多因子性遺伝子疾患の病因遺伝子を 特定する問題に対し、Quinlanが決定木生成でデータ分割のために 用いたエントロピー最小化に基づいて、病因遺伝子集合を論理積ルー ル（相関ルール発見における商品集合検索を連続値に拡張したような もの）として発見する並列アルゴリズムを開発した（詳しくは日本ソフト ウェア科学会第１５回大会併設チュートリアル「データマイニングの実装 と応用」ISSN 1341-8718 参照）。 このアルゴリズムでは最初に固定数のスレッドを生成し、探索木の兄弟 ノードを複数のスレッドで並列計算し、計算の結果できた子ノードをキュ ーイングすることを繰り返して計算を行うことで速度を上げている（だが 問題自体はNP困難）。StarFireでは毎回同じ実行時間で殆どリニアに 台数効果が出るが、Originではそううまくいかないらしい（DSMとSMPの 違い？）。 他にも決定木／回帰木の並列生成をやはりマルチスレッドで行っている。

知識発見を統合したシステム WebPACADE タンパク質の立体構造検索・解析・および 知識発見を統合したシステム WebPACADE 類似部分構造検索機能（PACADE) http://pacade.genome.ad.jp/pacade.html 可視化機能（PDB highlight） http://pacade.genome.ad.jp/pdb_highlight.html 簡易データマイニング機能 http://pacade.genome.ad.jp/cgi-bin/mining_form.pl これらのサービスは相互呼び出しを行っており ゲノムネット上でサービスされている（可視化 機能を提供する PDB highlight から入れる）

システムの構成と動作 WebPACADE PACADE PDB highlight structural sim. search data mining module structural sim. search assoc. rule discovery visualization links to foreign services links to foreign services input forms result of sim. search visual window result of mining user

WebPACADE がサポートするデータ PACADE PDB rel.80 から選んだ4842エントリのタンパク質の 二次構造に関するジオメトリ情報をファクトとして 格納している（約１７０万ファクト） PDB highlight ゲノムネットでの最新PDB（rel.84）を全てサポート （7688エントリ） 簡易データマイニング ゲノムネットが提供する LinkDB（異なるゲノムデータ ベースのエントリ間の参照関係）を用いて相関ルー ル発見を行うモジュール（LinkDBが提供する参照関 係の総数は約６６０万件）

PACADE による類似部分構造検索 可視化で使う プラグイン （フリーウェア） 類似元を 可視化 類似部分構 造を可視化 簡易データ マイニング

PDB highlight による可視化 他のデータベースの参照 一次構造 他の解析サービスの呼び出し 立体構造 プラグインを操作するこ とにより拡大縮小／回転 ／平行移動などが可能 二次構造

簡易データマイニングの模様 対象のゲノムデータ ベースを指定 PDBのエントリ集合 簡易データ マイニング 見つかった 相関ルール

WebPACADEの課題＝並列化 PACADEの類似構造検索自体が遅い（３０秒～５分程度） →CoralからPVMが使えるらしいので試してみる予定 構造上の類似性に基づいたタンパク質の網羅的な分類は 重要なテーマだが、PACADEでこれをやると大変 →HGCのStarFireを半分（32PE）使って all-to-all の検索 を実行した時は３週間かかった（出てきた類似関係の 総数は約１３００万） データマイニングモジュールはHPAのような並列化が必要 →現在は探索範囲とターゲットをユーザに指定させることで 爆発を回避している状態

おわりに ゲノム解析は「データがどんどん増えるので計算機資源が いくらあってもすぐに足りなくなってしまう応用領域」の典型 （Webのサーチエンジンに近いものがある） →並列化は必須の技術 キーワード検索やホモロジー検索など、日常的に利用する ものについては割合単純なデータ並列が有効（キャッシュも） データマイニングなど、Advanced な解析を行いたい場合は 組み合わせ爆発に陥るケースが多いので、アルゴリズムの 工夫が重要