平成２６年度東京大学・情報生命科学特別講義IIIのホームページ

講義予定

第1回： 文字列マッチング

KMPアルゴリズム、BMアルゴリズム、ACアルゴリズム

第2回： 文字列データ構造

接尾辞木、BW変換、接尾辞配列

第3回： たたみ込みとハッシュに基づくアルゴリズム

Don’t Careつきマッチング、Karp-Rabinアルゴリズム

第4回: 近似文字列マッチング

Landau-Vishukinアルゴリズム、Don’t Careつき近似マッチング、局所性鋭敏型ハッシュ

第5回: 配列アラインメント

大域・局所・線形領域アラインメント、マルチプル・アラインメントの近似

第6回: 配列解析

配列決定、最短拡大文字列、逆位によるソーティング

第7回: 進化系統樹推定

距離行列法、再節約法、最大合致部分系統樹

第8回: 木構造の比較: 順序木

編集距離、Kleinアルゴリズム、文字列編集距離による近似

第9回: 木構造の比較: 無順序木

特徴ベクトルを用いた近似、指数時間アルゴリズム、固定パラメータ・アルゴリズム

第10回: 文法圧縮

文字列・画像・順序木の文法圧縮

第11回: RNA二次構造予測

Nussinovアルゴリズム、Valiantアルゴリズムの利用、擬似ノット

第12回: タンパク質立体構造の比較と予測

立体構造アラインメント、格子モデルの近似アルゴリズム

第13回: 固定パラメータアルゴリズムと部分k木

頂点被覆問題、木分解

第14回: グラフの比較と列挙

Color Coding、順序木の列挙

第15回: まとめ

阿久津達也のホームページへ