情報科学の学び方バイオインフォマティクスの基礎として萩谷この時間の目標（１）情報科学というのはそもそもどのような学問であるか（おおよそ、学ぶべき科目としてどのようなものがあり、それがどのような関係になっているか、情報科学そのもののマップ）この時間の目標（２）それらが、バイオインフォマティクスで学ぶべきことと、おおよそどのような関係にあるか（例えば、配列解析や遺伝子発見のアルゴリズムをちゃんと理解するためには、情報科学の何々を勉強する必要あり、というようなこと）この時間の目標（３）情報科学において、上記（２）のようなことを勉強したいときに、教科書としてどのようなものがあるか、どのような講義が例えば東大（コンピュータ科学）の中で開講されているかこの時間の目標（４）それからこれは大変難しい問題ですが、バイオインフォマティクスの研究者や開発者としてこれから生きて行くためには、情報科学（のどの分野）をどの程度きちんと勉強すべきなのか、その指針や心構えみたいなものを示すバイオインフォマティクスのための情報科学の基礎 • • • • • • • • 計算機システムの基礎ネットワーク管理実学的プログラミングアルゴリズム形式言語情報理論・数理統計連続系アルゴリズム（数値解析）データベース・知識表現バイオインフォマティクス教育カリキュラム • http://www.jsbi.org/society/curriculum.pdf 計算機システムの基礎 • ハードウェア • コンピュータ・アーキテクチャ – CPU、キャッシュ・メモリ、メモリ – ハード・ディスク、入出力装置 • オペレーティング・システム – ファイル・システム、プロセス管理 • プログラミング言語 – コンパイラ、アセンブラ、ローダ・リンカ • コンピュータ・ネットワーク – インターネットネットワーク管理 • • • • • • • • オペレーティング・システムのインストールユーザ管理（UNIXならばNISサーバ）ファイルの共有（UNIXならばNFSサーバ）ネットワークの敷設ファイア・ウォールの構築ルーティング、ネーム・サーバメール・サーバ、Webサーバ、SSH 各種のアタックやウィルスへの対処プログラミング • 日常的プログラミング – C、Java – shell、perl • システム・プログラミング – C、Java、アセンブラ • 分散プログラミング – webプログラミング－ CGI – Java • 並列プログラミング – MPI たとえば、 • 実践バイオインフォマティクスゲノム研究のためのコンピュータスキル – – – – Cyntbia Gibas、Per Jambeck 著水島洋監修・訳明石浩史、またぬき訳オライリー・ジャパン II部ワークステーション－システム環境－アルゴリズム • データ構造とアルゴリズム – A.V.エイホ・J.E.ホップクロフト・J.D.ウルマン著 – 大野義夫訳 – 培風館 • アルゴリズムとデータ構造 – 理学部情報科学科４学期 • • • • 基本的なデータ構造とそのアルゴリズムソートアルゴリズムの解析法アルゴリズムの設計法基本的なデータ構造 • リスト、スタック、待ち行列、写像 • 木 – ２分木 • 集合 – – – – 辞書ハッシュ表優先度つき待ち行列、２分探索木トライ、平衡木、MFSET • 有向グラフ • 無向グラフ基本的なアルゴリズム • 有向グラフ – 最短経路問題 – 強成分 • 無向グラフ – コスト最小の極大木 – 関節点と二重連結成分 – グラフのマッチング • ソート – クイックソート、ヒープソート – ビンソート、基数ソート – 比較によるソートの下限アルゴリズムの設計法 • 分割統治アルゴリズム • 動的計画法（ダイナミックプログラミング） – ワールドシリーズの賭け率 – 三角形分割問題 • 欲ばりアルゴリズム – 巡回セールスマン問題 • バックトラッキング – ゲームの木・巡回セールスマン問題 • 局所的な探索アルゴリズム – 最小コストの極大木・巡回セールスマン問題動的計画法 • ワールドシリーズの賭け率 P(i,j): Aがシリーズに勝つまでにあと i 勝、 Bはあと j 勝という状況で、最終的にAがシリーズに勝つ確率 P(i, j) = 1, i=0 かつ j>0 = 0, i>0 かつ j=0 = (P(i-1, j) + P(i, j-1))/2, i>0 かつ j>0 0 7/8 1/2 3/4 1/2 1/4 1/2 0 0 0 1 1 1 動的計画法 • 三角形分割問題 • アラインメント二つ（複数）の文字列の比較 – 音声認識・文字認識 – DNAやタンパクの比較 GACGGATTAG と GATCGGAATAG ギャップ GA-CGGATTAG GATCGGAATAG 動的計画法 • 二つの配列 s と t の間の類似度 • a[i, j]: 部分配列 s[1..i] と t[1..j] の間の類似度 • a[i, j] = max{a[i, j-1] - g, a[i-1, j-1] + p(i, j), a[i-1, j] – g} – g: ギャップのペナルティ – p(i, j): s[i] と t[j] の類似度 DNA（RNA）の二次構造 • ベースペア i.j の集合 • k-ループ --- k 個のベースペアで囲まれたループ – 1-ループ • ヘアピン（hairpin） – 2-ループ • スタック（stack） • バルジ（bulge） • 内部（interior） – マルチ・ループ（multi-loop） • ループに対してエネルギーが割り当てられる。ヘアピンスタックバルジ 3-ループこれらの構造にエネルギーを割り当てる。（nearest neighborモデル）内部動的計画法 • W(i, j) : i 番目のベースと j 番目の間の最小エネルギー • V(i, j) : i と j がペアである場合の最小エネルギー • W(i, j) = min(W(i+1, j), W(i, j-1), V(i, j), min(W(i, k)+W(k+1, j)) ik<j • V(i, j) = min(eh(i, j), es(i, j)+V(i+1, j-1), VBI(i, j), VM(i, j)) – eh(i, j) : ヘアピンのエネルギー – es(i, j) : スタックのエネルギー動的計画法 • VBI(i, j) = min(ebi(i, j, i, j)+V(i, j)) i<i<jj i-i+j-j – ebi(i, j, i, j) : 内部ループのエネルギー – O(n4) になってしまう… • VM(i, j) = min(W(i+1, k)+W(k+1, j-1)) ik<j-1 – マルチ・ループのエネルギーが 0 の場合。 – そうでないと… バックトラッキング • すべての可能性を尽くして最適解を求める。 • ある可能性を調べた後、それを取り消して、（バックトラック）別の可能性を調べる。 • ゲームの木 x x x x o – 盤面を節、可能な手を辺とする木 o o – min-max法 x o x x x – α-β刈り x x o x x o • 巡回セールスマン問題 – 分岐制約探索法 o o x o x x x o o x o o o o 分岐制約探索法 • 巡回セールスマン問題 • ある可能性（辺）を選んだならば、解候補（巡路）の集合を、その可能性に従うものの集合と、従わないもののの集合に分ける。 • それぞれ、それまでの選択を制約として、解候補のコストの下限を求める。 • 下限が既知の解候補のコストよりも大きければ、その集合全体を棄却する。 3 3 a 4 3 4 8 e 2 b 6 c 5 d 6 すべての巡路 17.5 (a,b) 17.5 を含む巡路 (a,b)と(a,c) を含む巡路 (a,b)を含み (a,c)を含まない巡路 20.5 18 (a,b)と(a,d)を含み (a,c)を含まない 18 巡路 abecda 21 (a,b) 18.5 を含まない巡路 (a,c)を含み (a,b)を含まない巡路 (a,c)と(a,b) を含まない巡路 18.5 その制約のもとでのコストの下限 21 刈り取れる 3 3 a 4 3 4 8 e 2 b 6 c 5 d 6 タンパク質スレッディング • タンパク質の立体構造の予測法の一つ • 既知の構造と、構造が未知のアミノ酸配列をマッチさせる。 • コアセグメントがループ領域によって繋がった構造モデル • 制約 – ループ領域の長さの上下限 – アミノ酸に対する制約 • スコア関数 • 分岐制約探索法より新しい教科書 • Introduction to Algorithms – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest – The MIT Press and McGraw-Hill Book Company, 1989 • Computational Molecular Biology: An Algorithmic Approach – Peval A. Pevzner – MIT Press, 2000. 形式言語 • オートマトン言語理論計算論 I、II – J.ホップクロフト・J.ウルマン著 – 野崎昭弘・高橋正子・町田元・山崎秀記共訳 – サイエンス社 • 形式言語論 – 理学部情報科学科４学期 • 有限オートマトンと正則表現 • 文脈自由文法とプッシュダウン・オートマトン • チューリング機械有限オートマトンと正則表現 • • • • • • 有限状態系非決定性有限オートマトン正則表現正則集合に対する反復補題正則集合に対する決定手続き有限オートマトンの最小化有限オートマトン（Mealy型） 0/y p0 0/n 開始 0/n 1/n q0 1/n p1 1/y BLAST • Basic Local Alignment Search Tool • 局所的アラインメント（vs. 大域的…） – クエリ配列と類似の配列を配列データベース中でサーチ。 – クエリ配列から決定性有限オートマトンを生成。 • Mealy型（遷移によって受理）。 – オートマトンがヒットしたら、ヒットを含む局所的に最適のセグメント・ペアを求める。 • 最適セグメント・ペアの候補文脈自由文法とプッシュダウン・オートマトン • • • • • 文脈自由文法導出木 Chomskyの標準形 Greibachの標準形プッシュダウン・オートマトンと文脈自由言語 • Chomskyの階層チューリング機械 • • • • • チューリング機械計算可能な言語および関数 Churchの仮説帰納的および帰納的加算言語の性質万能チューリング機械と決定不能問題 • 計算の複雑性の理論 • 手におえない問題情報理論・数理統計 • 情報数学 – 理学部情報科学科４学期 – 情報理論 • 情報量、エントロピー – 符号理論 • 数理統計 – 特に、推定が重要。 – ベーズの決定理論 – マルコフモデル、隠れマルコフモデルパターン認識 • パターン情報処理 – 中川聖一著 – 丸善株式会社 – – – – パターン情報の符号化とデータ圧縮統計的パターン認識法構造的パターン認識法時系列・２次元パターンのマッチング法 » 動的計画法によるパターンマッチング » 隠れマルコフモデル（HMM） » ハフ変換によるパターンマッチング – 音声の認識と理解 – 画像の認識と理解 – パターン認識システムの評価法 0.2 0.3 0.5 A B 0.3 0.7 0.4 簡単な隠れマルコフモデルの例 0.3 C 0.3 バイオインフォマティクスでは… • Biological Sequence Analysis R. Durbin, S. Eddy, A. Krogh, G. Mitchison Cambridge University Press 医学出版阿久津たちの訳本「バイオインフォマティクス」がある： – ペアワイズアライメント – マルコフ連鎖と隠れマルコフモデル – HMMを用いたペアワイズアライメント – プロファイルHMMによる配列の分類 – マルチプルアライメント – 進化系統樹とその構成法 – 確率モデルにもとづく進化系統樹構成法 – 変形文法 – RNA構造の解析 – 確率統計の基礎事項連続系アルゴリズム（数値解析） • 連続系アルゴリズム – 理学部情報科学科３年次 • 基本的な数値計算アルゴリズム – ガウスの消去法 – ニュートン法 • 誤差の見積もり • 各種シミュレーション – モンテカルロ（メトロポリス） • 分子軌道法 • 分子動力学データベース・知識表現 • データベース論 – 理学部情報科学科４年次 – – – – – 関係データベース演繹データベースオブジェクト指向データベース分散データベースシステム－トランザクション管理問合せ最適化技術 • XML • データマイニング • 知能システム論 – 理学部情報科学科３年次 • 知識表現－オントロジー（第一回参照）教科書 • Database System Implementation – Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom – Prentice-Hall, 2000 • Principles of Data Mining – D. Hand, H. Mannila and P. Smyth – MIT Press, 2001 – ISBN 1-57735-027-8 最後に • バイオインフォマティクスの研究者や開発者としてこれから生きて行くための指針や心構え • 基礎的なことを優先して勉強する。 • 自分を枠にはめない。何にでも挑戦する勇気と柔軟さ。