新しい高速相同検索アルゴリズムを用いたゲノム解析ツールの開発 宇野 毅明 　（国立情報学研究所） 2007年 5月10日 国立遺伝学研究所

もし、相同領域を短時間で行えるようになるなら、 ゲノム解析（相同領域発見）の困難さ ・ ここ数十年の計算機の進歩は目覚しいものがあるが、ゲノムの解析を短時間で行うにはまだ不十分 　 ソフトにより性能は異なるが、100万文字の配列（文字列）２つを比較するのにもかなり（数分から数時間）かかる 　 染色体のような、数億文字ある配列の比較には多大な計算資源が必要 　 他にも、ショットガンシークエンスから行うアセンブリング、BAC配列の比較、固有な部分配列の同定など、計算資源を必要とする問題は多い もし、相同領域を短時間で行えるようになるなら、 それがゲノム研究に与える影響は大きい

アルゴリズム理論 ・ 計算の高速化において、並列計算は強力であるが、コストがかかるのが欠点 （プログラミングの複雑さも含め） 　アルゴリズム理論 ・ 計算の高速化において、並列計算は強力であるが、コストがかかるのが欠点　（プログラミングの複雑さも含め） ・ アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を、計算手法の設計変更により、抑える 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つは含む

ゲノムの比較 (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がない － 実験誤差データを考慮していない － オンラインサービスをするべき ・ 既存のソフトウェアとの連携を 進めていくべきだろう

問題設定：短い文字列の比較 問題： 各項目が同じ長さ 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以下のものを求めよ 例題 ・ 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

実は、情報の人間は良く知らない ・ 情報（特にアルゴリズム理論）の研究者の多くは、ゲノムの問題の実情を良くわかっていない、と思われる 　－ 最も重たい計算は、遺伝ネットワークでの最適化問題ではなく、相同検索である 　－ 相同検索は、全体をアラインメントで比較するだけでなく、部分的な比較を必要とする 　－ ゲノムの読み取りは、DNAをぶつ切りにしてつなぎあわせる 　－ BLAST、 phred/phrap/consed というソフトがある 　－ 単なる相同検索だけでなく、固有配列や反復配列の発見、オーバーラップの検出が必要である ・ しっかりと問題を聞かなければいけない

データベースから類似する項目を見つける ・ データベースの項目の中で、似た項目のペアを全て見つけたい （項目のペア全てについて、 2項関係が成り立つかを調べる） ・ 類似している項目の検出は、 　データベース解析の基礎的な手法 　　基礎的なツールがあれば、使い方しだいで いろいろなことができる （大域的な類似性、データの局所的な関連の構造・・・）

グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの (２部クリーク：完全２部グラフになっている部分グラフ) クリーク列挙問題 グラフのクリーク： 部分グラフで、全ての頂点間に枝があるもの 　　(２部クリーク：完全２部グラフになっている部分グラフ) ・ クリークは、グラフの中の密な構造をあらわす 　　クラスタ、コミュニティーなどをあらわす ・ 極大クリークの列挙は比較的高速にできる(秒速10万個） ・ クリークっぽい構造の列挙もできる

・ データベースの中に多く現れるパターンを頻出パターンという  データの解析、特徴分析、知識・ルール発見に使える 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを頻出パターンという 　 データの解析、特徴分析、知識・ルール発見に使える データベース 頻出する パターンを抽出 ・ 実験1● ,実験3 ▲ ・ 実験2● ,実験4● ・ 実験2●, 実験3 ▲, 実験4● ・ 実験2▲ ,実験3 ▲ 　　　　． 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT ・ ATGCAT ・ CCCGGGTAA ・ GGCGTTA ・ ATAAGGG 　　　　． 実験結果 ゲノム情報 ・ グラフ、木、文字列、時系列など、多くのパターンが扱える ・ 頻出パターンの列挙は、通常非常に高速で行える ・ 実験結果から分類規則を見つけることができる

各種最適化問題 最適化問題： 与えられた条件を満たす解の中で、評価値が最も良いもの、あるいはかなり良いものを見つける問題 ・ グラフ構造：パス、木、サイクル、クリーク、マッチング ・ 文字列構造： 部分文字列、シークエンス ・ 集合構造： カバー ・ 平面構造： 四角、直線、詰め込み、 ・ 問題によって、解法をデザインする必要があるが、比較的見通しが明るいことが多い

… 各種サブグラフ列挙問題 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ グラフのサイクル ・ 部分木 ・ マッチング ・ 全張木 ・ 高速だが、解の数が大きい ・ サイクルの代わりにコードレス サイクルを使う、といった工夫が必要 A B …

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