長崎大学工学部 情報工学コース 平成27年度後期: データ構造とアルゴリズム (水曜日2校時)
追加資料
> シーケンス・データ・マイニングの初歩
> 完全に一致する部分列を探す方法 ~ 力ずく法 (brute-force method)
GCCACCAAGTTCCGCACATGCCGGATAGAAT CCAAG x(1文字の比較でダメと分かったので,1文字分右にずらして,次。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCAAG ooox(4文字の比較でダメと分かったので,1文字分右にずらして,次。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCAAG ox(2文字の比較でダメと分かったので,1文字分右にずらして,次。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCAAG x(1文字の比較でダメと分かったので,1文字分右にずらして,次。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCAAG ooooo(見つかった!!!)
> 完全に一致する部分列を探す方法 ~ BMH(Boyer-Moore-Horspool)法
GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA x(Cで不一致。Cが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA xo(Aで不一致。Aは、いまチェックした位置より左にはもうないので、パターン全体を一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA x(Cで不一致。Cが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA xo(Cで不一致。Cが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA xo(Cで不一致。Cが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA x(Gで不一致。Gが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA x(Cで不一致。Cが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA x(Gで不一致。Gが出てくる一番右の位置まで、一気にずらす。) ↓ GCCACCAAGTTCCGCACATGCCGGATAGAAT CCGGA ooooo(見つかった!!!)
> おおよそ一致する部分列を探す方法 ~ 動的計画法
> おおよそ一致する部分列を探す方法 ~ Needleman-Wunschのアルゴリズム
HEAGAWGHE-E・・・横方向(黄色)の文字列 --P-AW-HEAE・・・縦方向(水色)の文字列
> おおよそ一致する部分列を探す方法 ~ Smith-Watermanのアルゴリズム
[戻る]
|