短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム 宇野 毅明　（情報研） 2004年1月30日 COMP研

ミスマッチトレランスとは ・ 文字列 L と ( L より短い) 文字列 S に対して L の中で S に最も似ている( S と同じ長さの)部分列との違いの大きさを「S のミスマッチトレンランス」という ・ 「似ている」の尺度には、ハミング距離を用いる 　　　　　ATGCCG　　　　 ATGCTG 　　　　　ATCCCG AATGCT 　　　　　　　距離1　 　　　　　　距離5

応用：ジェンチップとマイクロアレイ ・ 「DNAの中に、指定した20文字程度の部分列があると反応する試薬（ジェンチップ）」ができた ・ Q さんがXという遺伝子を持つか： 　　１．Xを20文字ずつにぶつ切り （オーバーラップするようにする）、 　　２．それらに反応するような試薬を作る 　　３．Q さんのDNAを入れて反応を見る ・ 全部に同じように反応するならば、 遺伝子があるだろう 遺伝子 QさんのDNA

精度の高い判定をするために ・標的の部分以外に類似する部分列があると、そこが反応してしまうかも ・なるべく固有な（似たものがない）部分列で判定したい ・ ミスマッチトレランスが大きい部分列に切る分ける

ミスマッチトレランスの既存研究 入力： 文字列 L と 文字列 S 出力： S のミスマッチトレランス ・O(|L|+|S|) 時間で簡単にできる ・suffix array のように、ある種のデータ構造を作成してから質問(Sのミスマッチトレランス)に高速に答えるようなことは難しいようだ　（Queryと呼ぶ。ほんとはこれがしたい） ・「ミスマッチトレランスの下界」なら、データ構造で質問に高速回答できる（O(|S|K)時間、Kはパラーメータ、定数）（山田森下02) ・一般のエディット距離でできるともっとうれしい

今回の問題 入力： 文字列 L と 長さk 出力： L の各部分列のミスマッチトレランス （文字種は定数とする。総ミスマッチ計算と呼ぶ） 　　（文字種は定数とする。総ミスマッチ計算と呼ぶ） ・普通に計算すると O(|L|2) 時間かかる ・ゲノムのような長い文字列に対しては、動かない 　　　　　　( 30億の2乗／1000MIPS ≒ 90億秒 ≒270年 ) ・もう少しオーダーの小さい、あるいは実際に速いアルゴリズムが欲しい

今回の結果 ・総ミスマッチ計算に対する O(|L|2k) 時間アルゴリズム （線形時間！K=20 なら 30億×100万、もとの300倍） ・実用的に高速にする改良 　　　　（K=20 なら 30億×100? 、もとの300万倍） ・こんなこともできる 　　・類似するペアを列挙（複数の文字列間も可） 　　　　　⇒　ゲノムの比較に使える！ 　　・O(|L|2k)メモリを使うと Queryが O(2k) 時間で解ける 　　・一般のエディット距離（係数が大きくなる）

基本のアイデア：類似の条件 子問題１： 各部分列 S に対して、異なりが d 文字以下の部分列があるか ・ Yes　⇔　 S と i1,…, ik-d番目の文字が等しい部分列がある 子問題２： i1,…, ik-dを固定。i1,…, ik-d文字目が等しい 他の部分列が存在する部分列を列挙 ・Radix ソートで O(|L|k) 時間 AC T CG T AC G CG A GA G TG A GA C TG C TG G TG A

基本のアイデア２：分類 子問題３： 全てのi1,…, ik-dに対して、i1,…, ik-d文字目が等しい 他の部分列が存在する部分列を列挙 AC T CG T AC G CG A GA G TG A GA C TG C TG G TG A

基本のアイデア２：分類 子問題３： 全てのi1,…, ik-dに対して、i1,…, ik-d文字目が等しい 他の部分列が存在する部分列を列挙 AC T CG T AC G CG A GA G TG A GA C TG C TG G TG A

基本のアイデア２：分類 子問題３： 全てのi1,…, ik-dに対して、i1,…, ik-d文字目が等しい 他の部分列が存在する部分列を列挙 O(|L|k kCd) 時間でできる AC T CG T AC G CG A GA G TG A GA C TG C TG G TG A p=0,…,k 全てについて行うと O(|L|k 2k) 時間

実用上の高速化 １ ・ 全てのi1,…, ik-dに対して、毎回律儀にソートする必要は無い 実用上の高速化　１ ・ 全てのi1,…, ik-dに対して、毎回律儀にソートする必要は無い ・ まず1文字目でソートしておけば、i1,…, ik-dが1文字目を含むなら、このソートの結果を共同利用できる ・ 同様に、再帰的に i文字目のソート結果を再利用できる ・ 何文字かでソートした際に、すでに等しい部分列がないものがでたら、以後それは考慮しなくて良い 　⇒　計算時間の短縮

実用上の高速化 ２ ！ 早めに共通部分のソートをした方が、同値類が小さくなる ・ 添え字集合 i1,…, ik-dを分類 実用上の高速化　２ ！ 早めに共通部分のソートをした方が、同値類が小さくなる ・ 添え字集合 i1,…, ik-dを分類 　１．k/2 以下の添え字がk/2+1 以上のものより同じか少ない 　２．k/2+1以上の添え字がk/2以下の添え字より少ない １．は 1,…,k/2 文字目を先にソート ２．は k/2+1,…,k 文字目を先にソート これを再帰的に繰り返す

実用上の高速化 ３ ・ 何文字かでソートした際に、すでに等しい部分列がないものがでたら、以後それは考慮しなくて良い 実用上の高速化　３ ・ 何文字かでソートした際に、すでに等しい部分列がないものがでたら、以後それは考慮しなくて良い ・ 何文字かでソートした際に、等しい部分列が少なくなったら、直接比較したほうが速い （等しい部分列のグループ　＝ 　同値類）

実用上の高速化 ４ ・ i文字目までをソートした ・ そこまでの同値類で、全てのメンバーのミスマッチトレランスがd以下だとすでにわかっている 実用上の高速化　４ ・ i文字目までをソートした ・ そこまでの同値類で、全てのメンバーのミスマッチトレランスがd以下だとすでにわかっている ⇒ その同値類は以後計算する必要はない

実験 ・ 東芝ノートPC ・ Pentium III 750MHz、RAM 256MB（実際は80MB） ・ C で組み、Windows上のLinux、Cygwin で実行 ・ Radix sort を2k 回行ったもの、改良1,2,3,4を順々に加えたものを比較 ・ d を k の1-2割とし、ミスマッチトレランスがそれ以上のものは「それ以上」とだけ答えるようにした （実用性＆計算時間から）

実験：k=20, d=2

実験：k=20, d=3

実験：k=40, d=4

実験：長さを200万、ミスマッチ率10% で固定、kを変化させる

Query に答える ・ 計算の再帰構造をメモリに記憶する ・ 与えられた文字列 S に対して、 S に関係する再帰だけをトレースすると、S を含む同値類が列挙できる 　　⇒ S のミスマッチトレランスがわかる ・ 人間のY染色体で行うと、10GBくらいのメモリを使うことになるようだ。

類似する部分列のペアを列挙 ・ 各 i1,…, ik-pでの同値類を計算し、大きさ2以上の同値類のメンバー同士は、ハミング距離がp 以下。そういうペアを全部出力 ・ ハミング距離がp 未満だと、複数回出力される （ちょうどp だと、ちょうど１回出力される） 　　⇒ ハミング距離がちょうどp のペアのみ出力 　　　　p を 1 から k まで順に大きくする ・ ゲノムAの部分列と B の部分列で似ているものを列挙、 ということもできる

一般のエディット距離に拡張 ・ 各 i1,…, ik-pでと j1,…, jk-pの組に対して、i1番目とj1番目、i2番目とj2番目,…,ik-p番目とjk-p番目が同じ部分列の組を見つければよい 　　　　　A T G C C G　　　　 A T G C T G 　　　　　A T C C C G A A T G C T 　　　　　　　距離1　 　　　　　　距離2

まとめ ・ 文字列の、長さ k の各部分列のミスマッチトレランスを線形時間で計算する、分類型アルゴリズムを提案した ・ 実用上速くなる手法を提案した （再帰的に分類、無用な再帰の省略） ・ 計算実験の結果を示した（ノートPCでも、何とかゲノムが扱える） ・ 類似する部分列のペアの列挙、一般の距離への拡張などの応用を示した