地球に優しいゲノム相同検索 宇野 毅明 （国立情報学研究所 ＆総合研究大学院大学） 2007年 12月3日 ミニシンポジウム：地球環境問題と計算限界 ゲノム相同領域発見問題 （注） ゲノム情報学の分野では、文字列の類似する部分を相同領 域、類似する部分を見つける問題（類似検索）を相同領域検索、 あるいは相同検索といいます ゲノムは種の進化や個体差、実験のエラーなどにより、同じ 機能を持つものでも、異なる形でコードされていることが多い そもそも、似たものを見つけるのも重要 － 機能が未知の遺伝子と類似する遺伝子を探す － 異なる種のゲノムの比較 （類似部分には意味がある） － ゲノム読み取り時に、断片配列をつなげる － 固有な部分配列の同定をして、マーカーとして使う － 同じく、プライマーとしてPCR増幅に使う ゲノムの読み取り ゲノムを読み取る方法 １． DNAを薬で溶かして、ひも状にする ２．放射線などを当てて、短い切片にぶつぶつ切る ３．機械で読む。1回で500文字程度読める ただし、精度は99.9%程度。1000文字に1文字くらいミスる ４．読んだ結果をつなぎ合わせて、もとのゲノムを構築する 系統樹作り ・ 各生物種が、どれくらい前に分かれたものかという、進化の系 統樹を推測する ・ ゲノムが似ているものは最近分かれた種である、という推測で 樹を作る ・ いくつかのまったく違う生物から大まかな樹を作るものと、ター ゲットとなる種を（例えばイネとか）決めて、その中でどのように 細かい種が分かれていったかを調べるものがあるようだ 最短路問題 ・ ２つのゲノムに対して、グリッド型のネットワークを作る ATGCA AGCAT ATGCA* A*GCAT 横移動 ： 左側に空白を挿入 縦移動 ： 下側に空白を挿入 斜め移動 ： 空白無し（同じ文字ならコスト０） A C G T A A G C A T 相同検索の応用と困難さ ・ 相同検索は、ゲノム解析における中心的な道具 計算のうち半分以上は相同検索とも… ・ しかし、類似検索なので計算資源が必要 現在は並列計算にたよっている ・ 類似検索なので、基本的に２分探索のような手法は使えない ソフトにより性能は異なるが、100万文字の配列（文字列）２つ を比較するのにもかなり（数分から数時間）かかる 染色体のような、数億文字ある配列の比較には多大な計算 資源が必要 （あるいはヒューリスティックでやる） もし、相同領域を短時間で行えるようになるなら、 それがゲノム研究に与える影響は大きい エネルギーの使用量 ・ 現在世界中に多くの分子生物学研究センター、グループが存在 日本では、国立遺伝学研究所、かずさDNA研究所、理化学研 究所、基礎生物学研究所(岡崎) 、などなど 大学の研究室や，製薬会社の研究所なども多数 ・ 多くがクラスタコンピュータを抱えている ・ クラスタコンピュータの消費電力は1ユニットあたり200W程度、 ・ 冷却や照明も含め、100ユニットで3万W程度 計算にエネルギーを多用している 効率化により、温暖化対策が可能 アルゴリズム理論からのアプローチ ・ 計算の高速化において、並列計算は強力であるが、コストが かかるのが欠点 （プログラミングの複雑さも含め） ・ アルゴリズム理論による高速化は、問題の大きさに対する計 算時間の増加を、計算手法の設計変更により、抑える 100項目 100万項目 2-3倍 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以下のものを求めよ A A A E F A G B B C F F F A C D C G G G B G A A A E F A A B B C F F F B C D C G G G A A A A E F G B C B F F F A C C D G G G B A A A A E F G B B C F F F A C D C G G G B 重複の回避 ・ まったく同じ文字列があると、全てのブロックの組合せで見 つかるので、 kCd 。回出力される 重複を回避する必要がある ・ 各見つかったペアについて、選択されていないブロックが選 択したブロックの間にあったら出力しないようにする 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる イメージ的には ・ 似ているもののペアを探す問題は、マトリクスのセルの中で必 要なものを全て見つける問題 ・ 全対比較は、マトリクスのセルをすべて見ていることに対応 ・ 分類によるアルゴリズムは、 分類を順々にしていると思えば、 木構造の探索を行っていることに対応 なぜBLASTより速くできるのか？ ・オリジナルのBLASTは、連続して11文字同じところを見つける 大雑把に言って、分類精度は、4の11乗 ≒ 400万 100万塩基あたりから苦しそう ・ 今回の手法は、例えば 30文字中間違い3文字（連続して7文 字同じ、と同じ精度）で6個に分割するなら、 大雑把に、分類精度は、4の15乗 ≒ 10億を20回 2億塩基あたりから苦しいが、そうなったら分割数を7にす ればいい ただし、(短い配列の）検索は苦手 （全部の比較と一部の比較の速度があまり変わらない） 実験：長さ20文字で異なり数 d を変化 人のY染色体から部分配列をとって実験。PenMのノートPC 10000 1000 d=0 d=1 d=2 d=3 10 20 00 70 00 22 95 3 0.1 70 0 1 20 0 計算時間(秒) 100 長さ(1000文字) ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 ・長さ3000万の配列×2 から、30文字の切片を3000万個取る ・ 似ている部分配列のペアの数に応じて、各ドットの明るさを変える ヒト 21番染色体 ・ 白い部分が 「似ている可能性のある部分」 チ ン ・ 黒い部分が パ 「(絶対に)似ていない部分」 ン ジ ・ 格子模様は、繰り返し 配列を拾っている PCで 1時間で可能 ー 22 番 染 色 体 ゲノムの比較 (2) X ヒトX染色体とマウスX染色体の比較 ・ 30文字で間違い2文 字以下のペアを列挙 ・ 長さ3000、幅300 の領域に3つペア があれば点を打つ マ （誤差10%弱で似て ウ ス いるものは、必ず３つ 染 のペアを含む） 色 体 ・ ノイズをかなり 除去できている PCで 2時間で可能 ヒトX番染色体 ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 ・ 一度に複数の ゲノムを比較できる PCで 1時間で可能 （マイクロアレイ用の）固有な配列のデザイン ・ マイクロアレイの設計には、ゲノム配列中でなるべく他の部分と 似ていない配列が使えるとありがたい ・ 配列の長さは２０文字、のように決まっているので、 対象となるゲノムの全て２０文字の部分配列を比較し、 似ているものがないもの、を見つければよい ・ 似ている文字列の数、はある種の統計量として利用できるかも しれない 100Mベース、25文字、間違い2文字まで、くらいなら PCで 1時間で可能 EST配列の比較 ・ 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、解の圧縮など） ・機能の追加 （特にアセンブリ）
© Copyright 2024 ExpyDoc
