Revision as of 01:24, 10 November 2010

生物情報学基礎論I

【授業計画】　各回の主テーマと、カッコ内に具体的なトピックを記す。

1. ガイダンス　（バイオインフォマティクスとは何か）[有田]
   1. フィボナッチ数列
   2. O記法
2. アルゴリズムと計算量　（計算量の記法、アルゴリズムの定義）[有田]
   1. PとNP
   2. チューリング機械
   3. クックの定理　（← 試験範囲外）
3. 分子生物学の基礎　（配列情報と生物学の関係）[有田]
4. 全解探索　（制限酵素マッピング、モチーフ探索）[有田]
   1. 教科書にある全解探索の見積もり方法を理解しておきましょう。
   2. 制限酵素マッピング
   3. モチーフ発見
5. 貪欲アルゴリズム　（ゲノムリアレンジメント、リバーサル）[笠原]
6. 動的計画法　（編集距離とアライメント、スコア行列）[笠原]
7. 動的計画法その２　（各種アライメント、最適化への応用）[笠原]
8. 分割統治法　（ブロックアライメント）[木立]
9. グラフアルゴリズム　（ハミルトン経路、タンパク質アラインメント）[笠原]
10. 組み合わせパターンマッチング　（ハッシュ、接尾辞木、接尾辞行列）[笠原]
11. クラスタリングと系統樹　（系統樹の構築と最適化の基準）[木立]
12. 隠れマルコフモデル　（ＨＭＭ，ＨＭＭアライメント）[木立]
13. 乱択アルゴリズム　（ギブスサンプラー）[木立]

教科書

“An Introduction to Bioinformatics Algorithms” Jones and Pevzner (MIT Press) 「バイオインフォマティクスのためのアルゴリズム入門」 Jones and Pevzner（著）、渋谷・坂内（訳）共立出版

評価方法

出席及び筆記試験。試験問題は授業を担当する各先生が作成します。

• 有田部分は、テキストに載っている簡単な事項に加え、授業内で解説した本ウェブサイト上の内容から出題します。ただし、Cookの定理の詳細と、授業で説明していないのにウェブ上で説明されている事項（例えばチューリング機械の等価性）に関する出題はありません。