新しい高速相同検索アルゴリズムを 用いたゲノム解析ツールの開発 宇野 毅明 （国立情報学研究所） 2007年 5月10日 国立遺伝学研究所 ゲノム解析（相同領域発見）の困難さ ・ ここ数十年の計算機の進歩は目覚しいものがあるが、ゲノムの 解析を短時間で行うにはまだ不十分 ソフトにより性能は異なるが、100万文字の配列（文字列）２つ を比較するのにもかなり（数分から数時間）かかる 染色体のような、数億文字ある配列の比較には多大な計算 資源が必要 他にも、ショットガンシークエンスから行うアセンブリング、 BAC配列の比較、固有な部分配列の同定など、計算資源を必要 とする問題は多い もし、相同領域を短時間で行えるようになるなら、 それがゲノム研究に与える影響は大きい アルゴリズム理論 ・ 計算の高速化において、並列計算は強力であるが、コストが かかるのが欠点 （プログラミングの複雑さも含め） ・ アルゴリズム理論による高速化は、問題の大きさに対する計 算時間の増加を、計算手法の設計変更により、抑える 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つは含む ゲノムの比較 (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がない － 実験誤差データを考慮していない － オンラインサービスをするべき ・ 既存のソフトウェアとの連携を 進めていくべきだろう 問題設定：短い文字列の比較 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータ ベースを入力したときに、文字列のペアで異なり数（ハミング距離）が d 文字以下である組を全て見つけよ ・ この問題を高速に解くアルゴリズム SACHICA （Scalable Algorithm for Characteristic/Homology Interval CAlculation ）を開発した （全対比較や類似検索よりも高速） ・ 長くて、ある程度似ている配列は、このような似ている部分列を必ず ある一定数以上含む ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA ．．． ・ ATGCCGCG と AAGCCGCC ・ GCCTCTAT と GCTTCTAA ・ TGTAATGA と GGTAATGG ．．． 問題の難しさ ・ 全ての項目が同じだと、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文字) 実は、情報の人間は良く知らない ・ 情報（特にアルゴリズム理論）の研究者の多くは、ゲノムの問題 の実情を良くわかっていない、と思われる － 最も重たい計算は、遺伝ネットワークでの最適化問題ではな く、相同検索である － 相同検索は、全体をアラインメントで比較するだけでなく、部 分的な比較を必要とする － ゲノムの読み取りは、DNAをぶつ切りにしてつなぎあわせる － BLAST、 phred/phrap/consed というソフトがある － 単なる相同検索だけでなく、固有配列や反復配列の発見、 オーバーラップの検出が必要である ・ しっかりと問題を聞かなければいけない データベースから類似する項目を見つける ・ データベースの項目の中で、似た項目のペアを全て見つけたい （項目のペア全てについて、 2項関係が成り立つかを調べる） ・ 類似している項目の検出は、 データベース解析の基礎的な手法 基礎的なツールがあれば、使い方しだいで いろいろなことができる （大域的な類似性、データの局所的な関連の構造・・・） クリーク列挙問題 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの (２部クリーク：完全２部グラフになっている部分グラフ) ・ クリークは、グラフの中の密な構造をあらわす クラスタ、コミュニティーなどをあらわす ・ 極大クリークの列挙は比較的高速にできる(秒速10万個） ・ クリークっぽい構造の列挙もできる 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを頻出パターンという データの解析、特徴分析、知識・ルール発見に使える データベース 実験1 実験2 実験3 実験4 ● ▲ ▲ ● ▲ ● ● ▲ ● ● ● ▲ ● ▲ ● ● ● ▲ ● ● ▲ ▲ ▲ ▲ 実験結果 頻出する パターンを抽出 ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT ゲノム情報 ・ 実験1● ,実験3 ▲ ・ 実験2● ,実験4● ・ 実験2●, 実験3 ▲, 実験4● ・ 実験2▲ ,実験3 ▲ ． ． ． ・ ATGCAT ・ CCCGGGTAA ・ GGCGTTA ・ ATAAGGG ． ． ． ・ グラフ、木、文字列、時系列など、多くのパターンが扱える ・ 頻出パターンの列挙は、通常非常に高速で行える ・ 実験結果から分類規則を見つけることができる 各種最適化問題 最適化問題： 与えられた条件を満たす解の中で、評価値が最も 良いもの、あるいはかなり良いものを見つける問題 ・ グラフ構造：パス、木、サイクル、クリーク、マッチング ・ 文字列構造： 部分文字列、シークエンス ・ 集合構造： カバー ・ 平面構造： 四角、直線、詰め込み、 ・ 問題によって、解法をデザインする必要があるが、比較的見通 しが明るいことが多い 各種サブグラフ列挙問題 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ グラフのサイクル ・ 部分木 ・ マッチング ・ 全張木 A ・ 高速だが、解の数が大きい ・ サイクルの代わりにコードレス サイクルを使う、といった工夫が必要 B … まとめ ・類似する項目のペアを列挙する、出力数依存型のアルゴリズム 異なりの場所に注目し、分類による絞込みを行う ・ 部分的な比較を用いて、大域的な類似構造を検出するモデル － ゲノムの比較： ヒト、チンパンジー、マウスの染色体の比較 バクテリアゲノムの多対多比較 － EST配列のマスク、オーバーラップ検出 － BAC配列の全対比較 － 固有部分配列の発見 ・ツールとしての完成度を高める（UI、解の圧縮など） ・機能の追加
© Copyright 2024 ExpyDoc
