| 序 文 i |
| 訳者まえがき v |
| 第 1 章イントロダクション 1 |
| 第 2 章アルゴリズムと計算量 7 |
| 2.1 アルゴリズムとは何か? 7 |
| 2.2 「生物学的アルゴリズム」と「計算機のアルゴリズム」 12 |
| 2.3 釣銭問題 15 |
| 2.4 「正しいアルゴリズム」と「正しくないアルゴリズム」 17 |
| 2.5 再帰的アルゴリズム 20 |
| 2.6 「反復アルゴリズム」と「再帰的アルゴリズム」 23 |
| 2.7 「速いアルゴリズム」と「遅いアルゴリズム」 28 |
| 2.8 Big-O記法 30 |
| 2.9 アルゴリズム設計のテクニック 32 |
| 2.9.1 全解探索 33 |
| 2.9.2 分枝限定法 34 |
| 2.9.3 グリーディー・アルゴリズム 34 |
| 2.9.4 動的計画法 34 |
| 2.9.5 分割統治法 38 |
| 2.9.6 機械学習 39 |
| 2.9.7 確率的アルゴリズム 39 |
| 2.10「手に負える問題」と「手に負えない問題」 40 |
| 2.11 補遺 41 |
| 研究者伝:Richard Karp 42 |
| 2.12 演習問題 44 |
| 第 3 章分子生物学入門 47 |
| 3.1 生命は何からできているか? 47 |
| 3.2 遺伝情報をもつものは? 48 |
| 3.3 遺伝子は何をするのか? 49 |
| 3.4 遺伝子が記されている分子はどの分子か? 49 |
| 3.5 DNA の構造はどのような構造か? 50 |
| 3.6 DNA からタンパク質へ何が情報を運ぶのか? 51 |
| 3.7 タンパク質はどのようにしてつくられるか? 52 |
| 3.8 DNA を解析するには? 54 |
| 3.8.1 DNA の複製 54 |
| 3.8.2 DNA の切断と接合 56 |
| 3.8.3 DNA 長の計測 57 |
| 3.8.4 DNA プローブ 58 |
| 3.9 種における個々の個体は何が異なるのか? 58 |
| 3.10 種と種は何が異なるのか? 58 |
| 3.11 なぜバイオインフォマティクスが必要か? 59 |
| 研究者伝:Russel Doolittle 62 |
| 第 4 章全解探索 65 |
| 4.1 制限酵素地図の作成 65 |
| 4.2 実用的でない制限酵素地図作成アルゴリズム 68 |
| 4.3 実用的な制限酵素地図作成アルゴリズム 69 |
| 4.4 DNA 配列中の制御モチーフ 71 |
| 4.5 プロファイル 72 |
| 4.6 モチーフ発見問題 75 |
| 4.7 探索木 78 |
| 4.8 モチーフを発見する 84 |
| 4.9 中央文字列を探す 86 |
| 4.10 補遺 89 |
| 研究者伝:Gary Stormo 91 |
| 4.11 演習問題 93 |
| 第 5 章グリーディー・アルゴリズム 97 |
| 5.1 ゲノム再編成 97 |
| 5.2 反転ソート 98 |
| 5.3 近似アルゴリズム 101 |
| 5.4 よりよいグリーディー戦略 102 |
| 5.5 グリーディー戦略によるモチーフ発見 105 |
| 5.6 補遺 106 |
| 研究者伝:David Sankoff 107 |
| 5.7 演習問題 110 |
| 第 6 章動的計画法 113 |
| 6.1 DNA 配列比較の威力 113 |
| 6.2 釣銭問題再考 114 |
| 6.3 マンハッタン観光客問題 117 |
| 6.4 編集距離とアラインメント 129 |
| 6.5 最長共通部分列 132 |
| 6.6 グローバル配列アラインメント 136 |
| 6.7 アラインメントのスコアづけ 137 |
| 6.8 ローカル配列アラインメント 138 |
| 6.9 ギャップペナルティーつきのアラインメント 141 |
| 6.10 マルチプルアラインメント 142 |
| 6.11 遺伝子予測 148 |
| 6.12 統計的な遺伝子予測のアプローチ 151 |
| 6.13 類似性に基づく遺伝子予測のアプローチ 153 |
| 6.14 スプライストアラインメント 155 |
| 6.15 補遺 158 |
| 研究者伝:Michael Waterman 160 |
| 6.16 演習問題 162 |
| 第 7 章分割統治アルゴリズム 173 |
| 7.1 ソーティングへの分割統治のアプローチ 173 |
| 7.2 省スペース配列アラインメント 175 |
| 7.3 ブロックアラインメントと4 人のロシア人の高速化 179 |
| 7.4 2乗時間より速いアラインメントの構築 181 |
| 7.5 補遺 182 |
| 研究者伝:Webb Miller 184 |
| 7.6 演習問題 186 |
| 第 8 章グラフ・アルゴリズム 187 |
| 8.1 グラフとは 187 |
| 8.2 グラフと遺伝学 196 |
| 8.3 DNA の配列決定 198 |
| 8.4 最短超文字列問題 199 |
| 8.5 DNA アレイを用いたシークエンシング法 200 |
| 8.6 SBH:ハイブリダイゼーションによるシークエンシング 202 |
| 8.7 SBH をハミルトンパス問題として解く 204 |
| 8.8 SBH をオイラーパス問題として解く 205 |
| 8.9 DNA 配列断片のアセンブリ 207 |
| 8.10 タンパク質の配列決定と同定 210 |
| 8.11 ペプチド配列決定問題 213 |
| 8.12 スペクトルグラフ 215 |
| 8.13 データベース検索によるタンパク質同定 216 |
| 8.14 スペクトル合成 218 |
| 8.15 スペクトルアラインメント 220 |
| 8.16 補遺 223 |
| 8.17 演習問題 225 |
| 第 9 章組合せパタンマッチング 231 |
| 9.1 リピート発見 231 |
| 9.2 ハッシュテーブル 232 |
| 9.3 完全一致パタン検索 234 |
| 9.4 キーワード木 236 |
| 9.5 接尾辞木 237 |
| 9.6 相同性検索のためのヒューリスティック 240 |
| 9.7 近似パタンマッチング 242 |
| 9.8 BLAST による配列データベース検索 244 |
| 9.9 補遺 245 |
| 研究者伝:Gene Myers 246 |
| 9.10 演習問題 249 |
| 第 10 章クラスタリングと系統樹解析 251 |
| 10.1 遺伝子発現解析 251 |
| 10.2 階層的クラスタリング 253 |
| 10.3 k-Means クラスタリング 256 |
| 10.4 クラスタリングと準クリーク 257 |
| 10.5 系統樹 261 |
| 10.6 距離に基づく系統樹作成 264 |
| 10.7 加算可能行列に対する系統樹作成 266 |
| 10.8 系統樹と階層的クラスタリング 269 |
| 10.9 特徴に基づく系統樹作成 271 |
| 10.10 節約度最小化の小問題 272 |
| 10.11 節約度最小化の大問題 275 |
| 10.12 補遺 277 |
| 研究者伝:Ron Shamir 280 |
| 10.13 演習問題 283 |
| 第 11 章隠れマルコフモデル 285 |
| 11.1 CG アイランドと「公正なカジノ」店 285 |
| 11.2「公正なカジノ」店と隠れマルコフモデル 287 |
| 11.3 HMM の解読アルゴリズム 289 |
| 11.4 HMM のパラメータ推定 291 |
| 11.5 プロファイルHMM アラインメント 292 |
| 11.6 補遺 294 |
| 研究者伝:David Haussler 295 |
| 11.7 演習問題 298 |
| 第 12 章確率的アルゴリズム 299 |
| 12.1 ソーティング問題再考 299 |
| 12.2 Gibbs サンプリング 301 |
| 12.3 ランダムプロジェクション 302 |
| 12.4 補遺 304 |
| 12.5 演習問題 305 |
| バイオインフォマティクスのツールを使う 307 |
| 参考文献 309 |
| 索 引 317 |
図書
