並列配列相同性検索プログラム「GHOST-MP」講習会（講義編）
2015年3月20日

東京工業大学 大学院情報理工学研究科

角田 将典、石田 貴士、秋山 泰

1

講師紹介

角田 将典
かくた まさのり

石田 貴士
いしだ たかし秋山 泰
あきやま ゆたか

東京工業大学 大学院情報理工学研究科 計算工学専攻
2

本日の予定• 13:00-13:05 ごあいさつ• 13:05-13:50 GHOST-MP講習• 13:50-14:00 休憩• 14:00-16:00 GHOST-MP実習

3

関連文献紹介• GHOST-MP関連文献– GHOSTX: Suzuki et al., (2014) PLoS ONE 9(8):e103833• 接尾辞配列を用いたアラインメント候補位置の高速探索– GHOST-MP: Kakuta et al., (in preparation)• GHOSTXの分散メモリ環境版、• 当グループの他の配列相同性検索関連文献– GHOXTM: Suzuki et al., (2012) PLoS ONE 7(5): e36060• GPUを用いた相同配列検索– GHOSTZ: Suzuki et al., (in press) doi: 10.1093/bioinformatics/btu780• 部分文字列のクラスタリングによるアラインメント候補位置の高速探索– GHOSTZ-GPU: Suzuki et al., (in preparation)• GHOSTZのGPU版

4

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

5

GHOST-MPとは• 配列相同性検索プログラム– 塩基配列やアミノ酸配列をクエリ、アミノ酸配列を検索対象とする– 感度が高く、高速な検索• GHOSTXアルゴリズム（Suzuki et al. 2014）による高速な検索• Message Passing Interface （MPI）とOpenMPによる並列化による計算資源の利用• 大量クエリ配列の並列検索を高速に行える– 1本のクエリ配列からなる検索では、恩恵は小さい

6

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

7

環境と細菌叢• ヒトをはじめとして動物の体表・体内や、土壌、海洋などの環境中には様々な微生物が存在する• 同じ環境内でも微生物集団（細菌叢）には多様性があり、環境と細菌叢は相互に影響を与えている– ヒト腸内の細菌叢同士を比べても、条件（個人、疾病、乳児の成長過程など）によって、細菌の組成が異なる• 環境と細菌叢の関係を調査するため、環境中の細菌叢の情報を明らかにする必要がある

8環境中の細菌叢のDNA Sequencingによる解析（１）塩基配列から様々な解析が可能

分類群・遺伝子の相対存在度による解析

パスウェイ解析

系統樹解析
9

環境中の細菌叢のDNA Sequencingによる解析（２）• マーカー遺伝子（16S rRNAなど）– 特定の遺伝子がsequencingの対象• 対象がマーカー遺伝子に限られるため、必要なシーケンシングデータは小さい– どのような細菌がどのくらい存在するか解析• メタゲノム– 細菌叢の全ゲノムがsequencingの対象• 全ゲノムが対象であるため、必要とされるシーケンシングデータが大きい– どのような細菌がどのくらい存在するか解析– どのような遺伝子がどのくらい存在するか解析• シーケンサの性能向上によって可能になった• メタゲノムデータの解析では、配列解析の対象となる配列数と塩基数が大きいため、高速な解析が要求される

10

DNA Sequencingの近年の傾向
DNA Sequencingコストの推移（ヒトゲノム）
Cost per genome
Cost per Genome (USD)$1.E+08$1.E+07$1.E+06

moore's law$1.E+05$1.E+04$1.E+03
2001

2004

2006

2009

2012

2014

DateWetterstrand KA. DNA Sequencing Costs: Data from the NHGRI Genome Sequencing Program (GSP)
Available at: www.genome.gov/sequencingcosts. Accessed Jan 10, 2015.

11配列相同性検索が解析で果たす役割

分類群・遺伝子の相対存在度による解析

パスウェイ解析

系統樹解析• 配列相同性検索は、読み取った塩基配列の由来する分類群や遺伝子ファミリ、機能などの推定に用いられる• 塩基配列のみでは、分類群や遺伝子に関する情報は不明• 配列相同性検索により、既知の類似配列を探し、それらを推定する
12

GHOST-MPの開発動機• メタゲノム解析の際の配列相同性検索に、多くの時間を要する
クエリ:
DB:

土壌メタゲノムのシーケンシングデータ (75bp x 72M reads)
NGS system (Illumina GAII)NCBI nr (about 5GB)
KEGG genes.pep (about 2GB)

NCBI BLASTX
on 144-core Intel Xeon PC cluster

約400時間高速な配列相同性検索が必要とされる
13

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

14

配列相同性検索• 進化的に類縁関係にある配列（相同配列） 、つまり、共通の祖先を有する配列では、機能が保存していると推定することができる• 配列相同性検索は、相同配列としてデータベースから類似配列を検索する手法
MSGALDVLQMKEEDVLKFMSGGLDVLQMKEEDVLKFMSGNLDVLQMKEEDVLKF...

MSGALDVLQMKEEDVLKF

クエリ配列
データベース

類似配列15

配列相同性検索（配列の類似性）• 塩基またはアミノ酸の類似性、挿入、欠失を考慮してアラインメントし、スコアを評価する
M
M

SS

GGA
N

546 -2L
L

D-V
V

L
LQQ4 -11 445score=5+4+6-2+4-11+4+4+5
欠失不一致を許容
完全一致の場合でも塩基、アミノ酸によってスコアが異なる
16配列相同性検索（候補探索）• 様々な方法が提案されている基本的には、類似配列の検索時間を短縮するため、高速に候補を探索した後、候補についてアラインメントの評価を行う

クエリ配列
アラインメント候補
データベース
配列

検出の容易な特に類似した領域を列挙

アラインメント

アラインメントの伸長17配列相同性検索（候補探索）
計算領域

特に類似した領域

クエリ

データベースSmith-Watermanなどで最適解を求める場合

特に類似した領域を見つけ、その部分のアラインメントを確定することで計算領域を削減できる

類似スコアが低くなった際に挿入・欠失の伸長を打ち切ることで、計算領域をさらに削減できる

18

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

19

GHOSTXアルゴリズム（１） Suzuki et al. (2014) PLoS ONE 9(8):e103833• アラインメント候補位置を高速に探索するアルゴリズムを提案し、これによって高速な相同性検索を実現した• 接尾辞配列（Suffix Array）というデータ構造を用いて、二分探索を行うことでクエリとデータベースの一部を比較するだけで、候補位置を見つけることができる。配列全てを突き合わせて比較しないため高速
T = abracadabra$
0: abracadabra$
1: bracadabra$
2: racadabra$
3: acadabra$
4: cadabra$sort
5: adabra$
6: dabra$
7: abra$8: bra$9: ra$
10: a$
11: $Suffix Array
11:
10:
7:
0:
3:
5:
8:
1:
4:
6:
9:
2:$
a$
abra$
abracadabra$acadabra$adabra$bra$
bracadabra$
cadabra$dabra$
ra$racadabra$ 20

GHOSTXアルゴリズム（２）クエリ配列
アラインメント候補
データベース配列

検出の容易な特に類似した領域を列挙

アラインメント

アラインメントの伸長

ここにクエリ配列とデータベース配列の接尾辞配列を利用することで、アラインメント候補を高速に列挙する

21

GHOSTXアルゴリズム（３）BLAST
Query sequences

K-mer(neighborhood words)

GHOSTX

finiteautomaton

SeedsearchGapless
extension

Query sequences

DB

Search K-mer substring
match by using finite
automaton

Gappedextension
Results

Suffix Array

DB

Suffix Array

SeedsearchGapless
extension

Search substring
matches with the scoremore than threshold bycomparing SA

Gappedextension
Results22

GHOSTXの精度と速度• 計算ノード1ノード、1スレッドを利用した場合• BLASTと比較し152倍高速• 近年開発されメタゲノム解析に用いられているRAPSearchと比較しても、同等の精度で高速に検索が行えた23

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

24

GHOST-MP(Kakuta et al. in preparation)• GHOSTXアルゴリズムを用いて複数の計算ノード上で大規模並列検索を行う• 特にスパコン「京」で実行することを念頭に開発• スパコンをはじめとして近年の計算機の高速化は計算ユニット（コア、ソケット、ノード）の増加によって行われているため並列計算に対応することは重要• 分散メモリ環境では計算ノード間でデータが共有できないため、ノード間のデータ移動をMPIを実装した

25

GHOST-MP• GHOSTXアルゴリズムの「京」の計算環境に対する最適化• メモリの確保・メモリアクセスの最適化• スレッド間の負荷分散の改善プログラム全体経過時間

1スレッド使用時に対する速度向上
26

GHOST-MP• 検索アルゴリズム自体はGHOSTXと同じため、精度に変化はない• BLASTの並列実装であるmpiBLASTと比較し、同じ計算機資源を用いて80-100倍高速であった• 「京」を用いた実験で使用コアの増加と共に32,000 CPUコアまで計算速度が向上

Strong scaling on TSUBAME 2.5

Strong scaling on K computer27

アジェンダ• GHOST-MPとは• GHOST-MPの開発動機– メタゲノム解析• 配列相同性検索• GHOSTXアルゴリズム• MPIによる分散メモリ環境での並列化• メタゲノム解析（GHOST-MPの応用として）

28

解析処理の概要
サンプルi

各サンプルごとにGHOST-MPでリード配列のKEGG Ortholog（KO）を推定し、サンプル内のKOの相対頻度を求める。
その後サンプルのKO相対存在度に基づいてサンプル間の比較を行う。

リード配列…

GHOST-MPによる配列相同性検索

KEGG DB

相対存在度

K01111
K022221.32e-5
3.38e-6…

…
…

遺伝子長で補正

KO…

K01111
K02222KO

KEGG Ortholog （オーソログ遺伝子のグループ）29

ヒト口腔内メタゲノム解析への応用• GHOST-MPを利用してHuman Metagenome Project（HMP）の公開するシーケンシングデータの解析を行った– 口腔内8部位、381サンプル、180億リード– 部位： 角化歯肉、硬口蓋、咽喉、口蓋扁桃、舌背、頬粘膜、歯肉縁上の歯垢、歯肉縁下の歯垢、唾液

L.M. Proctor, Cell Host & Microbe, 2011 30

HMP口腔メタゲノムデータ内訳
Site# of samples# of reads (x 106)

角化歯肉6331

硬口蓋00

咽喉7128

口蓋扁桃6129

舌背12710330

頬粘膜1071202

歯肉縁上の歯垢1186200

歯肉縁下の歯垢7137

唾液

323

Total3811848431

KO相対存在度によるサンプル間比較• 主成分分析を行った• 第３主成分までで、58%の累積寄与率• 第1、第3主成分で口腔内、口腔前庭、歯垢のデータの分布が異なることが分った
口腔口腔前庭歯垢

L.M. Proctor, Cell Host & Microbe, 201132