生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング

Slides:



Advertisements
Similar presentations
生物情報ソフトウェア特論 (3)近似文字列マッチング 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター.
Advertisements

組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム( 1 ) スケールフリーネットワーク 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター.
情報生命科学特別講義III (5)配列アラインメント
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
情報生命科学特別講義III (1) 文字列マッチング
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
情報生命科学特別講義III (8)木構造の比較: 順序木
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
黒澤 馨 (茨城大学) 情報セキュリティ特論(6) 黒澤 馨 (茨城大学) 2017/3/13 confidential.
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
奈良女子大集中講義 バイオインフォマティクス (6) モチーフ発見・隠れマルコフモデル
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮
Approximation of k-Set Cover by Semi-Local Optimization
Reed-Solomon 符号と擬似ランダム性
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
香川大学工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之
京都大学 化学研究所 バイオインフォマティクスセンター
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(5) 木構造データ間の編集距離
情報生命科学特別講義III (7)進化系統樹推定
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love
生物情報ソフトウェア特論 (1) 文字列マッチング・データ構造
情報生命科学特別講義III (11) RNA二次構造予測
k 個のミスマッチを許した点集合マッチング・アルゴリズム
生物情報ソフトウェア特論 (8) RNA二次構造予測
生物情報ソフトウェア特論 (3)近似文字列マッチング
情報生命科学特別講義III (4)近似文字列マッチング
生命情報学入門 配列のつなぎ合わせと再編成
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
情報生命科学特別講義III (2)文字列データ構造
九州大学大学院 情報学専攻特別講義 (9) ブーリアンネットワークの 解析と制御
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
情報セキュリティ  第11回 デジタル署名.
情報セキュリティ  第8回 RSA暗号.
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
Introduction to Soft Computing (第11回目)
5.RSA暗号 素因数分解の困難性を利用した暗号.
25. Randomized Algorithms
九州大学大学院 情報学専攻特別講義 (3) 配列解析
分子生物情報学(2) 配列のマルチプルアライメント法
A Simple Algorithm for Generating Unordered Rooted Trees
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
A path to combinatorics 第3章後半(Ex3.8-最後)
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
生物情報ソフトウェア特論 (8) RNA二次構造予測
Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号,量子コンピュータ
人工知能特論II 第8回 二宮 崇.
九州大学大学院 情報学専攻特別講義 (8) ニューラルネットワークの 離散モデル
奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹
香川大学創造工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学創造工学部 富永浩之
情報生命科学特別講義III (14) グラフの比較と列挙
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
Q q 情報セキュリティ 第6回:2005年5月26日(金) q q.
生物情報ソフトウェア特論 (4)配列解析II
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
分子生物情報学(0) バイオインフォマティクス
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング 生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

講義予定 第1回: 文字列マッチング・データ構造 第2回: たたみ込みとハッシュに基づくマッチング 第3回: 近似文字列マッチング 第1回: 文字列マッチング・データ構造 第2回: たたみ込みとハッシュに基づくマッチング 第3回: 近似文字列マッチング 第4回: 配列解析 第5回: 木構造の比較:順序木 第6回: 木構造の比較:無順序木 第7回: 文法圧縮 第8回: RNA二次構造予測 第9回: タンパク質立体構造の予測と比較 第10回: 固定パラメータアルゴリズムと部分k木 第11回: グラフの比較と列挙 第12回: ニューラルネットワークの離散モデル

たたみ込みによる 文字列マッチング

たたみ込みとFFT ベクトル a=(a0,…,am-1) と b=(b0,…,bn-1) のたたみ込み a*b は            を要素とするベクトル c=(c0,…,cn+m-1) (ただし、cn+m-1=0と定義) 2つの多項式 の積 の各係数は、たたみ込みベクトルの各成分に等しい (a0,…,am-1) と (b0,…,bn-1) のたたみ込みはFFTを用いて (Real-RAM上で) O(n log n) 時間で計算可能(ただし、m≦n)

たたみ込みによる文字列マッチング: アイデア (a0, a1,a2) と (b0,…,bn-1) のたたみ込みを考える ここで、 a0, a1,a2 を逆順にすれば、以下のようになる ⇒ パターンを逆順にして、たたみ込みを行えば、   文字列マッチングに使えそう (Fisher-Patersonアルゴリズム)

たたみ込みによる文字列マッチング Σ={a,b}, T = abbabbab, P=abb, P-1=bba として、 χa(T)などを次のように定義 すると この2個のベクトルの和は 0131131120 となり、 値が 3 となる桁がマッチしている場所に対応 定理:文字列マッチングは FFT により O(n log m) 時間で実行可能 (ただし、|Σ|は定数)

Don’t Care記号つき文字列マッチング KMP, BM, ACアルゴリズムを Don’t Care記号つきに拡張するのは困難。でも、たたみ込み法なら、以下の例のように簡単 χa*(...) は、対象の文字が a か * なら、1 に対応させる 定理:Don’t Care記号つき文字列マッチングは FFT により O(n log m) 時間で実行可能 (ただし、|Σ|は定数)

Karp-Rabinアルゴリズム

ランダマイズド・アルゴリズム(乱拓アルゴリズム) 同じ入力を与えても、アルゴリズムの動作が内部で用いた乱数の値により異なるアルゴリズム ラスベガス・アルゴリズム 常に正しい解を出力(ただし、計算時間は乱数により異なることがある) モンテカルロ・アルゴリズム 誤った解を出力する可能性がある

Karp-Rabinアルゴリズム: アイデア ハッシュ関数の利用 長さ m の各部分文字列に対し、以下の性質を満たす 整数値(ハッシュ値)           を計算

Karp-Rabinアルゴリズム: ハッシュ関数 q を適当に大きな素数とし、b を適当な基数(例: b=2)とすると なお、h()は、毎回計算しなおさなくても、 により、1回あたり O(1) 時間で計算可能 定理: q を適当な範囲内でランダムに選ぶことにより、どのような     入力 P, T に対しても、高い確率で以下が成立 Karp-Rabinアルゴリズム ハッシュ関数を計算し、一致している場所を出力 ⇒ 線形時間モンテカルロ・アルゴリズム

Karp-Rabinアルゴリズム: 確率の解析 補題: 任意の N について、(異なる)素因数の個数は O(log N) (証明) 素数は2以上なので、t 個の素因数を持てば N≧2t 補題: x,y (x≠y) をそれぞれ m ビットの数とする。τ 以下の素数 p     をランダムに選んだ時、(x = y) mod p となる確率は (証明) (x = y) mod p となるのは |x-y| が p の倍数の時のみ。 一方、|x-y| の素因数の個数は上記補題より O(m) 個。 τ 以下の素数の個数は素数定理より≈ τ/ln τ なので、 (x = y) mod p となる確率は     。 (Karp-Rabinの定理の証明) τ = n2m log n2m とすれば、             なのに、ハッシュ値が一致してしまう i の存在確率は

ラスベガス・アルゴリズム化 方法1 マッチが見つかったら O(m) 時間かけてチェック 誤りであれば、単純なO(mn)時間アルゴリズムを   最初から実行 計算時間の期待値は O((m+n)+(1/n)(mn))=O(m+n) 方法2 マッチが見つかったら O(m) 時間かけてチェック 誤りであれば、異なる素数 p を用いて再実行 計算時間の期待値は O(m+n) 注意: 素数生成のための時間は考慮していないが、考慮しても定理や解析は成立

まとめ たたみ込みによる文字列マッチング Karp-Rabinアルゴリズム 補足 Don’t care 文字が扱える。  O(n log m) 時間 Karp-Rabinアルゴリズム ハッシュ関数を用いたランダマイズド・アルゴリズム 補足 たたみ込みマッチングは、文字のミスマッチにも対応可 たたみ込みを用いずに don’t care つき文字列マッチングを効率的に扱うのは(たぶん)研究課題 Karp-Rabinアルゴリズムは広くは利用されていないが、文字列などのデータをハッシュするという考え方は、第3回に説明する Locality Sensitive Hashingや埋め込み(Embedding)などの名で盛んに研究・応用されている 本講義で研究課題としたものはすべて「たぶん」です