令和４年度東京大学・生物情報ソフトウェア特論のホームページ

令和６年度版は こちら

講義予定

第1回： 文字列マッチング・データ構造

KMPアルゴリズム、BMアルゴリズム、ACアルゴリズム、接尾辞木、接尾辞配列

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

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

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

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

第4回: 配列解析I, II,

配列のマルチプル・アラインメントの近似、SETHによる編集距離計算量の下限、最短拡大文字列、逆位によるソーティング

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

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

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

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

第7回: 文法圧縮

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

第8回: RNA二次構造予測

Nussinovアルゴリズム、Valiantアルゴリズムの利用、O(n^{3-c})時間アルゴリズム

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

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

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

頂点被覆問題、木分解

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

Color Coding、順序木の列挙

第12回: ニューラルネットワークの離散モデルI, II

閾値関数の個数、閾値ネットワークの素子数、ReLU関数の表現力、自己符号化器

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