文字列の類似構造発見問題と 複数分類アルゴリズム 宇野 毅明 国立情報学研究所 ＆ 総合研究大学院大学 （修士・博士課程学生募集中） 2010 年 2 月 15 日 東京大学コンピュータ科学専攻講演 簡単に自己紹介 名前： 宇野 毅明 年齢・職種：国立情報学研究所・准教授・39歳 研究分野： アルゴリズム理論とその応用 － グラフアルゴリズムを中心とした離散アルゴリズム － 組合せ最適化とそれにまつわる数理 － 列挙アルゴリズムと、頻出パターンマイニングへの応用 最近の研究： ゲノム情報学やデータマイングで出てくる巨大なデー タベースの基礎的（とはいっても非常に時間のかかる）な解析を超 高速で行うアルゴリズムの開発 もっとー： 速い安い（単純）うまい 日課： 子供の世話と遊ぶこと 河原林さんと比較すると • グラフアルゴリズムは研究範囲、異なるところは、 － バックグラウンドはアルゴリズム・計算 － （残念ながら）最高峰の会議には通らず －落としどころが数理でない （簡単な結果を求める） • 同じ所は、共同研究のオファーが多いところ マーケッティング（経済）、カーナビ、ソーシャルネットワーク分析、 ロジック・・・ データベース、デーマイニング、分子生物学、情報化学 も • 今日は大量データに対する計算の話をします。 大量の文字列データ • 近年、大量の文字列データが簡単に蓄積されるようになりました。 － 電子化された書籍、新聞、雑誌 － Webなどの多数の人間が書いたテキストデータ － 特許文書や論文の文書 － OCRなどで読み取った過去の社内文書 － ヒトゲノムを始めとするゲノム情報 • データが大きすぎて、線形時間程度の処理しかできない ＋ 索引付けと（キーワード）検索 ＋ 圧縮・展開 ＋ 文字数・文字種・n-gram のカウント、分布 ＋ 文単位の、単語切り出し、構文理解・・・ • 複雑な、組合せ的な処理はほとんど出来ていない IT系(?)のアプローチ • それでも、情報学の研究者やIT企業は、大規模テキストデータを使っ ていろいろなことをしている ＋ Web検索、データベースの構築 ＋ 自動文書分類、文書ランキング、評判分析、話題抽出、 ＋ 類似文書の検出、おすすめの表示 （リコメンデーション） • どれも、小さいデータにある種の処理を行ない、それをデータベース に登録するタイプ （グーグルランクを除く） • 逆に、全体を眺めるような処理は行なわれていない － 話題の伝搬、引用関係 － （部分的に）似た文書の検出、固有な文書の検出 － 頻出するフレーズの発見 部分的な類似構造を検出できたら、一気にできることが増えそう 文書以外のデータでも • ゲノム情報学の分野では、ゲノム情報（実際は文字列データ）を を解析している • やはりできていることは単純なことで、複雑な解析は難しい ＋ 完全一致をベースとした検索・比較 ＋ 遺伝子の推定・・・ • 類似性の解析ができることで、効率化が進むものは多い － 機能が未知の遺伝子と類似する遺伝子を探す － 異なる種のゲノムの比較 （類似部分には意味がある） － ゲノム読み取り時に、断片配列をつなげる － 固有な部分配列の同定をして、マーカーとして使う － 同じく、プライマーとしてPCR増幅に使う ゲノムの読み取り ゲノムを読み取る方法 １． DNAを薬で溶かして、ひも状にする ２．放射線などを当てて、短い切片にぶつぶつ切る ３．機械で読む。1回で500文字程度読める ただし、精度は99.9%程度。1000文字に1文字くらいミスる ４．読んだ結果をつなぎ合わせて、もとのゲノムを構築する 類似性のモデル • ゲノムの変化（変異、あるいは実験での読み取りエラー）は、 局所的には、1文字単位で起きる • 既存研究では、文字列の尺度で類似度を判定している （コスト付き）編集距離 （ときどき）ハミング距離 • 両者ともに、数理的に美しい尺度であり、計算も容易 － 長さ n の文字列の比較 ハミング距離： O(n) 時間、 編集距離 O(n2) 時間 • 実際には、大域的な入れ替わり構造がある 相同検索（類似文字列検索）の困難さ • 相同検索は、ゲノム解析における中心的な道具 計算のうち半分以上は相同検索とも… • しかし、類似検索なので計算資源が必要 現在は並列計算にたよっている • 類似検索なので、基本的に２分探索のような手法は使えない ソフトにより性能は異なるが、100万文字の配列（文字列）２つ を比較するのにもかなり（数分から数時間）かかる 染色体のような、数億文字ある配列の比較には多大な計算 資源が必要 （あるいはヒューリスティックでやる） もし、相同領域を短時間で行えるようになるなら、 それがゲノム研究に与える影響は大きい 類似構造発見の研究（アルゴリズム的） • フィンガープリントを使った類似検索 （特徴量が一致するものを検索） （ざっくり言って）文章単位しか狙っていない 類似するからと言ってフィンガープリントが一致するとは限らない • BLASTを始めとする相同発見アルゴリズム （例えば11文字の）短い完全一致領域を見つけ、そこを種として検索 文字列が長いと、大量の完全一致がある 11文字を長くすると精度が落ちる 良く現れる単語は候補から除外、遺伝子部分だけ注目 といった処理をしているようだ • 類似検索 大量のクエリを実行しなければならない 類似検索は通常、完全一致検索より大幅に時間がかかる アルゴリズム理論からのアプローチ • 計算の高速化において、並列計算は強力であるが、コストが かかるのが欠点 （プログラミングの複雑さも含め） • アルゴリズム理論による高速化は、問題の大きさに対する計 算時間の増加を、計算手法の設計変更により、抑える （もとから線形時間のタスクは取り組む意味がない） 100項目 100万項目 2-3倍 10000倍 アルゴリズム理論から、類似構造発見に取り組んでみる 問題のモデル化とアルゴリズム 何がほんとに似ているか • 生物系の研究者に聞くと、編集距離は（距離が大きいと）研究者の直 感に対応していないようだ （テキストでもそのようだ） 同じ編集距離（ハミング距離）でも、似てる感が大きく違う ATGCATGCATATATATATGCATGC ATGCATGCGCGCGCGCATGCATGC ATGCATGCATATATATATGCATGC AAGGAAGGAAAAAAAAAAGGAAGG • どうも、部分的に集中して似てるところが効いているようだ • あまり短い部分だけが似ていても、意味がないようだ • さらに、実用上は「似ている部分が見つかればいい」ので、解の中に「 似ていない部分が混ざっていてもいい」 （見つけ損ないはダメだが、偽者を見つけても大きな被害はない） • まずは、短い類似構造を全部見つけることを考えよう 短い文字列の比較 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデ ータベースを入力したときに、文字列のペアで異なり数（ハミング 距離）が d 文字以下である組を全て見つけよ • ゲノム全体から各ポジションを先頭とする長さ l の部分文字列 を全て集めてこの問題を解くと、似ている部分列が全て見つかる • 新しいアルゴリズムを提案 (Sachica : Scalable Algorithm for Characteristic/Homologenous 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以下のものを求めよ ABCDE ABDDE ADCDE CDEFG CDEFF CDEGG AAGAB A A A C C C A BCDE BDDE DCDE DEFG DEFF DEGG AGAB A A A C C C A BC BD DC DE DE DE AG DE DE DE FG FF GG AB ABC ABD ADC CDE CDE CDE AAG DE DE DE FG FF GG AB 計算量について • ソートの部分は基数ソートで O(l |S|) 時間 • 基数ソートの1文字分ソートする部分を、複数のソートで共有する ようにすると、ソート一回当たりの時間は O((l/k) |S|) に減少する • 分類にかかる時間は、トータルで O((l/k) |S| kCd) 時間 • 全対比較の部分は、できたグループの大きさによるので、平均 的なことしか言えない、が、 • もし k=l ならば、グループ内の全てのペアは似ている、となる １つのペアが kCd 回見つかるので、計算時間は O((|S| + dN) kCd) となる （N は見つかるペアの数） 重複の回避 • まったく同じ文字列があると、全てのブロックの組合せで見 つかるので、 kCd 。回出力される 重複を回避する必要がある • 各見つかったペアについて、選択されていないブロックが選 択したブロックの間にあったら出力しないようにする 等しいブロックが一番左端によっている場合にのみ出力 メモリに解を保持せずとも、重複が回避できる k の選択 • 一番良い k をあらかじめ計算するのは不可能（と思われる） • どの k が良いか推定する問題を解いて、選ぶ • 2つの文字をランダムに選んだときの一致する確率を元に、l/k 個 の文字を使ってグループ分けしたときの、各グループのメンバーの 平均値を計算 • それを元に、計算コストを算定する。これを全ての k について行っ てベストなものを選ぶ なぜ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文字) 実験： 長さ30で、異なり数 d を変化させる 日本語webテキストデータ, Core2duo, E8400 3GHz, 4GB RAM 30,0text Japanese 1000 30,1 30,2 100 time, time/#pairs (sec) 30,3 30,4 10 30,0 ave 30,1 ave 1 30,2 ave 30,3 ave 30,4 ave 0.1 1366 2556 5272 10637 21046 40915 letters (1000) 長さ l が大きい場合 • l および k が大きくなると、ソートの回数が増えるため、計算は遅 くなる （1000文字中異なりが100、とか） 複数分類法と同じアイディアで高速化できる • 長さ l の文字列を h 個に分割する ２つの文字列の距離がk 以下なら、必ず距離がk/h 以下のブ ロックが存在 • k の選択と同じように、計算コストを算定して最適な h を選ぶ 分割の効能 • 1000文字でハミング距離100以下の組を見つけるとする • k=103 ブロックに分割とすると、103個の中から3 個を選ぶ組合せ はおよそ 100*100*100/6 で15万通りくらい • 3つのブロックの文字数は およそ29 文字。(文字種^29) 程度のグ ループに分類 • h=10 とし、k=14 としてその中から 6 個を選ぶとすると、ソート回数 は 14*13*12*11/4*3*2*1 ＝およそ1000通り（コストが150 分の1 ×10回） • ブロック4つの文字数はおよそ29 文字なので、グループ数は同じ 類似構造の可視化 何がほんとに似ているか • 生物系の研究者に聞くと、編集距離は（距離が大きいと）研究者の直 感に対応していないようだ 同じ編集距離（ハミング距離）でも、似てる感が大きく違う ATGCATGCATATATATATGCATGC ATGCATGCGCGCGCGCATGCATGC ATGCATGCATATATATATGCATGC AAGGAAGGAAAAAAAAAAGGAAGG • どうも、部分的に集中して似てるところが効いているようだ • あまり短い部分だけが似ていても、意味がないようだ • さらに、実用上は「似ている部分が見つかればいい」ので、解の中に「 似ていない部分が混ざっていてもいい」 （見つけ損ないはダメだが、偽者を見つけても大きな被害はない） ドットプロットによる可視化 • 大域的な類似構造を捕らえるためには可視化が良い • ドットプロットという可視化手法がある； 画像の横軸と縦軸を比較 したい文字列に対応させ、類似する部分に対応するピクセルに点を 打つ • もし長い類似構造があると、 それは部分的な対角線として 可視化される string A String B • 点の色の濃さを、対応する 部分列の組の中に含まれる 類似部分列の組にする 比較する部分列は、全ての ポジションから取る ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 • 長さ3000万の配列×2 から、30文字の切片を3000万個取る • 似ている部分配列のペアの数に応じて、各ドットの明るさを変える • 白い部分が 「似ている可能性のある部分」 チ ン • 黒い部分が パ 「(絶対に)似ていない部分」 ン • 格子模様は、繰り返し 配列を拾っている 通常のPCで 3分 ジ ー 22 番 染 色 体 ヒト 21番染色体 ゲノムの比較 (2) • ちょっと違いが大きなゲノムを比較してみる； マウスの11番染色 体とヒトの17番染色体の比較を、少し誤差の許容を大きくしてみる と… PCで3分 残念ながら何も見えない • 各文字列について「10個 の相手としかペアを作ら ない」とすると、少し見える まだまだノイジーだし、 正確性を失っている Human 17th chr • 短いノイズのような多量の類似 部分列が全てを隠している Mouse 11th chr. 同じくらいの明るさの点 • 同じ程度の明るさのピクセルでも、中の類似文字列のペアがど のように分布しているかはわからない • ペアが対角線に並んでいるところに興味がある 分散しているやつらはいらない 一部分に集中してしまっている物も興味がない • 対角線的なペアのみを取り出すために、凝った方法を考えるとき りがないので、簡単な方法でやってみる 長方形フィルター • 対角線方向に傾けた、長方形の箱を考える (長さが α で幅が β) もし、その箱の中にある程度のペアが入るなら、対角線上に並 んでいると考えていいだろう • しかし、ペアがある一点に集中していたら、それは良くない • ある箱の置き方に対して、ペアが閾値以上、集中せずに含まれ るようなとき、それらのペアを残し、任意の箱の置き方に対してそ のようにならないペアを消す 新しいモデル • ２つの文字列の類似を「似ている短い区間がいくつかある」で定義 （距離ではなく、似ているかいないかの２値になる） • この条件は、ある意味で、 既存の類似性の条件を弱めている • 既存の意味での類似性の下界にもなる 例：長さ3000でハミング距離が10%弱 (間違い290)なら、長さ30で間違い2の部分列を、少なくとも3つは含む • 離れた位置にある部分が似ていても全体が似ていることにはならない ので、ずれの最大をβで制限する • ２つの文字列が似ている部分文字列を持つ 「長さα、幅βの領域に閾値以上の類似部分文字列のペアがある」 ということになる 効率良く計算できるか • 類似部分文字列を持つ長さα幅βの領域をどう見つけるか ペア長さαの部分文字列を全対比較 ２乗の時間かかる 別の方法を考えないと、とても解けない • 最初に、短くて似ている部分 文字列のペアを全部見つけておく • 幅２βの斜めの線に沿って、長さαの領域に 閾値以上のペアがあるところを探す • 斜め線をβずつずらして、全ての部分について似ている部分を探す • 長さα幅βの似ている部分列は必ず見つかる(そうでないものも発見) • 短くて似ている部分列を効率良く見つければよい 箱フィルタを使ってもう一度 • もう一度、マウスの11番染色体とヒトの17番染色体の比較をして みる • 箱の長さ、幅、閾値を 3000, 300, 3 にしてみる • ノイズがほぼ取れている PC で3分 Human 17th chr • 画像の画素数を大きく すれば、さらにノイズを 取り除ける Mouse 11th chr. さらに大きな比較 Mouse X chr. マウスXとヒトX 染色体の比較 (両者1.5億文字) Note: BLASTZ で2週間 MURASAKI だと 2-3 時間 ただし誤差が1% だそうです。 Human X chr PCで15分 ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 • 一度に複数の ゲノムを比較できる PCで 1時間で可能 多数の比較結果を、色を変えて合成 • ある文字列を固定し、それと、他の文字列を比較して、結果 を（色を変えて）重ね合わせると、固定した文字列が他のどこ と対応するかがわかる ヒト22番染色体 マウスの全ての染色体 （全て左端から開始、右端は長さに応じて変化） PCで6時間程度（3GB） 中規模類似構造の発見 長い類似文字列の検出 • 長い類似文字列は、必ず短い類似文字列を含む 短い類似文字列を見つけて、それを伸ばせばよい • ただし、伸ばす際の計算時間と、重複の回避（似たものが沢山 出てこないようにする）が問題 － ハミング距離なら、１つ伸ばすのに1演算 O(1) － 編集距離だと、１つ伸ばすのに異なり数 O(d) • ハミング距離が d 以下の極大な文字列は、似たものが沢山 XXXXXXAAAAAAAAAXXXXXX OOOOOOAAAAAAAAAOOOOOO • 「端が異なりなら伸ばさない」というルールを入れてもだめ XAXAXAXAXAXAXAXAXAXAXAXAX OAOAOAOAOAOAOAOAOAOAOAOAO • 閾値を割合にしたり、編集距離を使っても同じことが起きる 連続区間ハミング距離 • 極大が定義しやすい新しい類似の尺度を導入しよう •パラメータとして、長さ l を用意 • ２つの文字列 S と S’ に対して、距離を「始まり位置が同じであ る長さ l の部分文字列の最大ハミング距離」で定義 ______ S AAAXAAAAAAAXXAAAXAAAAAXAAAAAAA l=6 S’ AAAOAAAAAAAOOAAAOAAAAAOAAAAAAA • 「連続区間ハミング距離」だと、似たものは絶対に出てこない ２つの類似区間が(長さ 以上の)重なりを持つなら、 2つを合わせた物も類似区間になる つまり、「計算しやすくて極大が少ない」 重複の排除 • 極大な連続区間ハミング距離が d の文字列組は、長さ l でハミ ング距離が d 以下の文字列組を見つて伸ばせば、見つかる 任意の長さ l の部分文字列は、ハミング距離が d 以下なので • 逆に見れば、同じ極大文字列が何回も見つかってしまう メモリに既発見を取っておいてチェックすると、伸ばす計算と検 索の時間、損をする ______________________________ S AAXAXXXXXAAAXAAAAAAAXXAAAXAAAAAXAAXXXAXXAXA l = 6 S’ AAOAOOOOOAAAOAAAAAAAOOAAAOAAAAAOAAOOOAOOAOA • そこで、代表を決める 「自分の左には伸ばせない」 「代表は一人だけ」 「代表であるか、簡単にチェックできる」 • 代表を見つけたときだけ、極大文字列を出力すると、 自動的に重複を回避できる 比較する部分文字列の省略 • 少し長めの類似構造を調べたいときには、比較する部分文字 列を省略しても効果がある － 、適当な k と h を定め、比較する文字列AとB （両者が同じこ ともあり得る）から、A の部分文字列を kh 文字おきに連続 k 個 、B から k 文字置きに選び出して比較 － どのような、長さ kh 以上の部分列の組でも、かならず一つ比 較される部分列を含む 任意の部分列の組に対して A B このように部分列が比較される 計算コストの比較 • たとえば l=50である連続区間ハミング距離を用いて、450文字 以上の類似構造を見つけたいのであれば、k=20,h=20 としても、 450文字のどこかが見つかるため、そこから左右に類似部分を伸 ばすことで、450文字以上の構造は必ず発見される • 短い類似文字列を見つける問題自身は、比較する文字列の数 が 1/20 になるので、20倍以上高速化される • 比較する文字列 A,B の長さに偏りがある場合、例えば|A|=25|B| であれば、k=100,h=4 とすることで、比較する文字列の数を |A|/100 + |B|/4 に減少できる。これは |A|+|B| のおよそ1/100 類似構造拡張のコスト • 重複を回避するために、左方向に類似構造を伸ばす。他のシ ードが見つかったら、その時点でやめる。他のシードにたどり着く 前に類似構造の端に来たら、類似構造を見つけた、として出力 • シードを見つける 類似構造を拡張する 以前に見つけた ものでなければ出力 という方法だと、長さ |H| の類似構造が z 個のシードを含むと すると、類似構造の拡張にかかる手間は O(z|H|) • 対して、先の重複回避と同じ方法を使うと、同じ場所は高々1回 しか比較されない。よって手間は O(|H|) マウスとヒトの比較 • マウスの染色体全部とヒトの染色体全部を比較。長さ50、異な り数1、計算時間は10時間ほど ACATTTGGTACAAATCCACTCTTCACCCCTTCCCAGCCCTCCTGGATTGTAATC TCCCCCCTTTTAACCAGCTCATATATGTCTCTTGTCAGGTCTGTGAAGGCTTTC TCCACATTAATGGCATCTCGGGCTGACGTTTCAATGTACTTCATGCCGTATGCA GCAGCCAGTTTCTCGGCCTCGTGGCGAGTCACTTGCCTCTGTGTATCCAGGTCA CACTTGTGACCCACCAGAACAAATACAATTTGGTAGGGCTGAACGTGTACTTTG GTCTCTTCTAACCACTCATGGACATTCTGGAAGGACCTGCGGTTGGTAATGTCA AATAAGAGAAGACCACCTACTGAGTTCCTGTAGATGTCAAATAAGAGAAGACCA CCTACTGAATTCCTGTAGTAGGCGCGAGTGATGGATCTAAAACACAAGAAAGAA GTAAAGAGTAAAG • 染色体同士に対応があると、 300文字以上の類似領域がけっ こう（1-10）見つかる マウスとヒトの比較 • これくらいなら、完全一致を見つけるアプローチでも何とかなる。 そこで、異なり数を3にしてみる、計算時間は20時間ほど ACATTTGGTACAAATCCACTCTTCACCCCTTCCCAGCCCTCCTGGATTGTAATC TCCCCCCTTTTAACCAGCTCATATATGTCTCTTGTCAGGTCTGTGAAGGCTTTC TCCACATTAATGGCATCTCGGGCTGACGTTTCAATGTACTTCATGCCGTATGCA GCAGCCAGTTTCTCGGCCTCGTGGCGAGTCACTTGCCTCTGTGTATCCAGGTCA CACTTGTGACCCACCAGAACAAATACAATTTGGTAGGGCTGAACGTGTACTTTG GTCTCTTCTAACCACTCATGGACATTCTGGAAGGACCTGCGGTTGGTAATGTCA AATAAGAGAAGACCACCTACTGAGTTCCTGTAGATGTCAAATAAGAGAAGACCA CCTACTGAATTCCTGTAGTAGGCGCGAGTGATGGATCTAAAACACAAGAAAGAA GTAAAGAGTAAAG • 染色体同士に対応があると、 500文字以上の類似領域がけっ こう（1-10個）見つかる （これはイメージ） 頻出文字列の発見 • 最近は、「あちこちに現れる構造」「同じような物が繰り返している 構造」に注目が集まっている（ようだ） 似ている文字列の発見から、「良く現れる文字列を見つける」 という問題を解いてみたい • ところがこの問題が非常に難しい + 良く現れるとはどういうことか + 長さはどうするか。短いのから長いのまで全部考慮するのか + 境目はどこにするか、似たものが沢山出てきたらどうするか + どうやって速く計算するか • 既存の研究のアプローチではほとんど失敗している 頻出する文字列パターンの発見 境目はどこにするか • 似たような文字列がたくさんあり、それぞれの終了位置が異なる とき、どこが終了かを決めるのは難しい 非常に多くの揺らぎがある • 簡単なアプローチで攻めることにしよう 似ている物がたくさんある物を中心に • 先のアルゴリズムで、長さ l の文字列それぞれに対して、似てい る物がどれくらいあるかは調べられる • 似ている物がたくさんある文字列は、たぶん頻出する物の中心 になっているだろう それを中心に伸ばしてみよう • 伸ばすときには、類似性を使って伸ばすと大変なので、 単に多数決を取ることにしよう 頻出文字列を核にする ① 最も似ている物が多いもの S を見つける ② S と似ている物を全て集める ( S1,…,Sm) ③ それらをそろえて並べ、文字が共通している部分を抜き出す 次に進む • 一番良く現れる物について頻出文字列を見つけたら、次に「2番 目に良く現れる文字列」について同じことをする • ただし、見つけた頻出文字列を求めるのに使った文字列は、候 補から消去する • 「類似部分文字列組」が計算してあれば、これらの計算は非常に 短時間でできる + （候補文字列の中から）最も良く現れる物を見つける + それに似ているものを全て見つける 計算結果 • マウス13番染色体 Genic1 での実験結果(150万文字)。長さ30異 なり数2、多数決の閾値は 70%。10回以上現れるもののみ注目 #T#GCAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTTATGATATCTGA #TTGCAAAGGCTTTACCACATTGATTACATTCATAAGGTTT#TCTCCAGTATGG#TTCTTTTATGATATCTGA GAC#A#TGTGACAGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT GATTACTGTGA#AGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT #TGATATCTGAGACTA#TGTGACAGGAAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTA ATGA#ATTGGAGAT#A TGGGTTCTTTTATGATAT#TGAGAC#A #TCTCTGAA#AAAGAAAT#AAAGAAGATCTCAGAAGATGGAAAGATCTCCCATGCTCAT#GATTGGCAGGATC AATATAGTAAAAATGGCTATCTTGCCAAAAGCAATCTACAGATTCAATGCAATCCCCATCAAAAT#CCAACT# AATTCTTCA • # は多数決が決まらない場所、計算時間は10秒ほど まとめ • ハミング距離が短い文字列の組を見つける、高速アルゴリズム • 類似性の性質に基づいたフィルタリングを利用した可視化 • 極大が見つけやすい、新しい類似尺度を提案 • 良く現れる文字列を、似ている物が沢山ある短い文字列を核に して、多数決を取ることで発見 • 実際にゲノムで比較を行い、既存の方法よりはるかに短時間で ある程度の保証をもつ解を得た 課題 • ツールとしての完成度を高める（UI、解の圧縮など） • このアルゴリズムを利用した解析システム（特にアセンブリ） まとめ • min-wise independence やベクトルとの内積の符号など、「類似す ると一致する可能性が高い指標」をランダムに複数用いて文字列 を作り、文字列のハミング距離が短いものを見つけることで、短時 間で高い精度で類似するものを見つける方法の提案 • ベクトルデータと集合データ • sachica を利用して高速計算 • 繰り返し計算による精度向上 どなたかいいデータ （多量の項目からなるベクトルデータ） 持って ないでしょうか？
© Copyright 2024 ExpyDoc
