宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学） 地球に優しいゲノム相同検索 宇野 毅明 　（国立情報学研究所 　　　　　　　＆総合研究大学院大学） 2007年 12月3日 ミニシンポジウム：地球環境問題と計算限界

ゲノム相同領域発見問題 （注） ゲノム情報学の分野では、文字列の類似する部分を相同領域、類似する部分を見つける問題（類似検索）を相同領域検索、あるいは相同検索といいます 　 ゲノムは種の進化や個体差、実験のエラーなどにより、同じ機能を持つものでも、異なる形でコードされていることが多い 　 そもそも、似たものを見つけるのも重要 － 機能が未知の遺伝子と類似する遺伝子を探す － 異なる種のゲノムの比較　（類似部分には意味がある） － ゲノム読み取り時に、断片配列をつなげる － 固有な部分配列の同定をして、マーカーとして使う － 同じく、プライマーとしてPCR増幅に使う

ゲノムの読み取り ゲノムを読み取る方法 １． DNAを薬で溶かして、ひも状にする ２．放射線などを当てて、短い切片にぶつぶつ切る ３．機械で読む。1回で500文字程度読める 　ただし、精度は99.9%程度。1000文字に1文字くらいミスる ４．読んだ結果をつなぎ合わせて、もとのゲノムを構築する

系統樹作り ・ 各生物種が、どれくらい前に分かれたものかという、進化の系統樹を推測する ・ ゲノムが似ているものは最近分かれた種である、という推測で樹を作る ・ いくつかのまったく違う生物から大まかな樹を作るものと、ターゲットとなる種を（例えばイネとか）決めて、その中でどのように細かい種が分かれていったかを調べるものがあるようだ

・ ２つのゲノムに対して、グリッド型のネットワークを作る 最短路問題 ・ ２つのゲノムに対して、グリッド型のネットワークを作る 横移動　　：　左側に空白を挿入 縦移動　　：　下側に空白を挿入 斜め移動 ：　 空白無し（同じ文字ならコスト０） ATGCA AGCAT A C G T ATGCA* A*GCAT A　G　C　A　T

もし、相同領域を短時間で行えるようになるなら、 相同検索の応用と困難さ ・ 相同検索は、ゲノム解析における中心的な道具 　 計算のうち半分以上は相同検索とも… ・ しかし、類似検索なので計算資源が必要 　 現在は並列計算にたよっている ・ 類似検索なので、基本的に２分探索のような手法は使えない 　 ソフトにより性能は異なるが、100万文字の配列（文字列）２つを比較するのにもかなり（数分から数時間）かかる 　 染色体のような、数億文字ある配列の比較には多大な計算資源が必要　（あるいはヒューリスティックでやる） もし、相同領域を短時間で行えるようになるなら、 それがゲノム研究に与える影響は大きい

エネルギーの使用量 ・ 現在世界中に多くの分子生物学研究センター、グループが存在 　 日本では、国立遺伝学研究所、かずさDNA研究所、理化学研究所、基礎生物学研究所(岡崎) 、などなど 　 大学の研究室や，製薬会社の研究所なども多数 ・ 多くがクラスタコンピュータを抱えている ・ クラスタコンピュータの消費電力は1ユニットあたり200W程度、 ・ 冷却や照明も含め、100ユニットで3万W程度 計算にエネルギーを多用している 効率化により、温暖化対策が可能

アルゴリズム理論から、相同領域発見に取り組んでみる 　アルゴリズム理論からのアプローチ ・ 計算の高速化において、並列計算は強力であるが、コストがかかるのが欠点　（プログラミングの複雑さも含め） ・ アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を、計算手法の設計変更により、抑える 100項目 2-3倍 100万項目 10000倍 データが巨大になるほど、アルゴリズム改良の加速率は上がる アルゴリズム理論から、相同領域発見に取り組んでみる

ゲノム情報学の計算面での到達点 ・ ゲノム情報学の問題、解けるようになったでしょうか？ 情報学的には： 「基礎的なものは解けてます」 　「基礎的なものは解けてます」 　「知識発見など、複雑な問題が解けないですね」 生物学的には： 　「計算ができなくて困っています」 　「難しいことより、まず簡単なことができないんです」 ・ 非常に大きなギャップがある ・ 聞き込みをしてみると、「計算量がわかっても意味がない」「研究のフォーカスがずれている」「実装がない」「基礎的な問題が解きたいが、（モデル化、あるいはアルゴリズム的な意味で）筋が違う」 などなど （考慮する要因や、問題の定式化など）

相同領域発見の研究（アルゴリズム的） ・ ２つ文字列の編集距離（挿入／削除／変化の最小数）は最短路アルゴリズムを使って、ある程度高速に求められる 　　２つの文字列が似ていないと有効でない 　　入れ替わり構造は発見できない ・ BLASTを始めとする相同発見アルゴリズム （例えば11文字の）短い完全一致領域を見つけ、そこを種として検索 　　文字列が長いと、大量の完全一致がある 　　11文字を長くすると精度が落ちる 　　良く現れる単語は候補から除外、遺伝子部分だけ注目 　　　　といった処理をしているようだ ・ 類似検索 　　大量のクエリを実行しなければならない 　　　　類似検索は通常、完全一致検索より大幅に時間がかかる

アルゴリズムからモデル・定式化へ アルゴリズム 問題 ・ 通常、モデル化（定式化）とアルゴリズムは、解ける問題と解きたい問題のすりあわせして、うまい落としどころを見つける ・ しかし、相同性検索では、状況が少し違うようにみえます 　 「うまく解ける問題」を単純に拡張しただけ ・ 完全一致の検索がうまくできる、うまく評価できる類似性の尺度がある、という２つを単純に組み合わせただけ ・ アルゴリズムの視点から問題の定式化を見直せば、よりうまく解けるモデルが提唱できるかも アルゴリズム 問題

問題設定：短い文字列の比較 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータベースを入力したときに、文字列のペアで異なり数（ハミング距離）が d 文字以下である組を全て見つけよ ・ この問題を高速に解くアルゴリズム SACHICA （Scalable Algorithm for Characteristic/Homology Interval CAlculation ）を開発した （全対比較や類似検索よりも高速） ・ 長くて、ある程度似ている配列は、このような似ている部分列を必ずある一定数以上含む ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

ゲノムの比較 ・ 比較するゲノムを、オーバーラップさせてスライスし、全対比較 ・ 縦横に比較するゲノムをおき マトリクスを作って類似するペアが あるセルの色を白くする（各ピクセル内の 個数によって色の強弱をつける） ・ 長さα、幅βの領域にいくつかのペアが あるときのみ、色を白くする  長さαの部分配列が、誤差 k %弱で 似ているなら、必ず 誤差 k %で似て いる短い部分列がいくつかある 例：長さ3000で10%弱(間違い290)なら、 長さ30で間違い2の部分列を、少なくとも3つは含む

問題の難しさ ・ 全ての項目が同じだと、O(項目数2) 個の出力がある  l を定数だと思えば、単純な全対比較のアルゴリズムが 　　　　　計算量の意味では最適になる 　  計算量理論的には面白くない問題 ・ 現実には、やたらと似ているものがあるものを比較しても意味が無い 　  出力は少ないと仮定する ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA 　　．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG 　　　　 ．．．

基本のアイディア：文字列の分割 ・ 各文字列を、k（>d） 個のブロックに分割する ・ k-d 個のブロックの場所を指定したときに、そこがまったく等しくて、かつハミング距離がd 以下となるようなペアを全て見つけよ、という部分問題を考える  各文字列の k-d 個のブロックをつなげてキーにし、ソートをする。同じものはグループになる。それを総当りで比較すればよい ・ k-d 個のグループ数が大きければ、平均的にグループのメンバー数は小さくなるので、総当りで比較してもたいしたことない

全ての場合を尽くす ・ 先の部分問題を、全ての場所の組合せについて解く  ２つの文字列が似てれば、必ずどこか k-d 個のブロックが同じ  必ずどれかの組合せで見つかる ・ 部分問題は、バケツソートやRadixソートで速く解ける ・ 組合せの数は kCd 。のk=5 で d=2 なら10通り 　　 ソート10回 ＋α で解ける。全対比較よりもかなり高速 ・各文字の数から、１文字比較した場合に等しくなる確率を求め、適切な分割数 k を使用する

・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ 例題 ・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ A B C A B D A C C E F G F F G A F G G A B G A B A B C A B D A C C E F G F F G A F G A B C A C C A B D A F G E F G F F G G A B A B C A B D A C C A F G E F G F F G G A B

メモリに解を保持せずとも、重複が回避できる 重複の回避 ・ まったく同じ文字列があると、全てのブロックの組合せで見つかるので、 kCd 。回出力される 　 重複を回避する必要がある ・ 各見つかったペアについて、選択されていないブロックが選択したブロックの間にあったら出力しないようにする 　 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる

イメージ的には ・ 似ているもののペアを探す問題は、マトリクスのセルの中で必要なものを全て見つける問題 ・ 全対比較は、マトリクスのセルをすべて見ていることに対応 ・ 分類によるアルゴリズムは、 分類を順々にしていると思えば、 木構造の探索を行っていることに対応

（全部の比較と一部の比較の速度があまり変わらない） なぜBLASTより速くできるのか？ ・オリジナルのBLASTは、連続して11文字同じところを見つける 　 大雑把に言って、分類精度は、4の11乗 ≒ 400万 　 100万塩基あたりから苦しそう ・ 今回の手法は、例えば 30文字中間違い3文字（連続して7文字同じ、と同じ精度）で6個に分割するなら、 　大雑把に、分類精度は、4の15乗 ≒ 10億を20回 　 2億塩基あたりから苦しいが、そうなったら分割数を7にすればいい ただし、(短い配列の）検索は苦手 （全部の比較と一部の比較の速度があまり変わらない）

人のY染色体から部分配列をとって実験。PenMのノートPC 実験：長さ20文字で異なり数 d を変化 人のY染色体から部分配列をとって実験。PenMのノートPC

ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 ・長さ3000万の配列×2 から、30文字の切片を3000万個取る ・ 似ている部分配列のペアの数に応じて、各ドットの明るさを変える ・ 白い部分が 「似ている可能性のある部分」 ・ 黒い部分が 「(絶対に)似ていない部分」 ・ 格子模様は、繰り返し 　　配列を拾っている ヒト 21番染色体 チンパンジー22番染色体 PCで 1時間で可能

ゲノムの比較 (2) ヒトX染色体とマウスX染色体の比較 ・ 30文字で間違い2文 字以下のペアを列挙 ・ 長さ3000、幅300 の領域に3つペア があれば点を打つ （誤差10%弱で似て いるものは、必ず３つ のペアを含む） ・ ノイズをかなり 除去できている ヒトX番染色体 マウスX染色体 PCで 2時間で可能

バクテリアを30種 ABC順の取得し つなげて比較 ・ 一度に複数の ゲノムを比較できる ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 ・ 一度に複数の ゲノムを比較できる PCで 1時間で可能

（マイクロアレイ用の）固有な配列のデザイン ・ マイクロアレイの設計には、ゲノム配列中でなるべく他の部分と似ていない配列が使えるとありがたい ・ 配列の長さは２０文字、のように決まっているので、 対象となるゲノムの全て２０文字の部分配列を比較し、 似ているものがないもの、を見つければよい ・ 似ている文字列の数、はある種の統計量として利用できるかもしれない 100Mベース、25文字、間違い2文字まで、くらいなら PCで 1時間で可能

1万 EST で、PCで 10分で可能 （向きを考えれば5000） ・ EST配列(500文字程度？)をつなげて contig を作るときには、どことどこがつながるかを調べるために、どことどこが似ているかを調べる必要がある （重なり部分が端まで来ているもののみを見つける必要がある） ・ 似ている部分、ではなく、ほとんど同じ、でよいので、計算は多少楽） ・ マスクをかける、といったこともできる 1万 EST で、PCで 10分で可能 （向きを考えれば5000）

反復配列の検出 ・ 1つの文字列の内部を比較して、似てる部分を見つけたら、それを出力せずに、数を勘定することにする  各位置について、「何回現れるか」がわかる ・ 最後に、「5回以上現れた部分配列で100文字以上のもの」のように指定して出力すると、反復配列の候補が出る 今までのものとほぼ同じ計算時間

BAC配列の比較 ・ ゲノム全体の配列を決める際には、BAC同士がどのようにつながるかを調べる必要がある ・ しかし、どの配列とどの配列がオーバーラップしているか調べるのは、大変。（前述のアセンブリをミスしていると、微妙に異なるところが出て、重ならなくなる） ・ 例えば、重なりそうな BACのアセンブリをやり直す ことで、より正確なContig が 作れるかもしれない PCで 1ペア1秒

（生物学的な）課題点 ・ マウス13番染色体の未解読領域に適用を行っている  既にいくつかの空白部分が埋まった ・ 比較は高速にできるようになった。だが、比較結果をどう使うか、何に留意する必要があるか、といった点は、まだまだ明らかでない － 実験の指針を出すためには、 　　何を出力する必要があるか － どの程度の精度が必要か － どこまで処理を自動化すべきか － エラーをどのように扱うべきか  既存のアセンブリングソフト (phred/phrap/consed)では見つからない、 特殊な重なり方をしている相同領域が 見つかる。どう解釈すべきか？

（情報学的・システム的な）課題点 ・ 相同検索としての能力は高い ・ しかし、細かい部分で既存のソフトに劣る － アラインメントが取れない － ゲノム固有の制限を入れていない － データベースと連携していない － インストーラ、GUIがない － 実験誤差データを考慮していない － オンラインサービスをするべき ・ 既存のソフトウェアとの連携を 進めていくべきだろう

まとめ ・類似する項目のペアを列挙する、出力数依存型のアルゴリズム 異なりの場所に注目し、分類による絞込みを行う 　　異なりの場所に注目し、分類による絞込みを行う ・ 部分的な比較を用いて、大域的な類似構造を検出するモデル 　－ ゲノムの比較：　ヒト、チンパンジー、マウスの染色体の比較 　　　　　　　　　　　　　バクテリアゲノムの多対多比較 　－ EST配列のマスク、オーバーラップ検出 　－ BAC配列の全対比較 　－ 固有部分配列の発見 ・ツールとしての完成度を高める（UI、解の圧縮など） ・機能の追加　（特にアセンブリ）