確率文脈自由文法と RNA二次構造予測  確率文脈自由文法   HMM（正規文法に相当）の文脈自由文法への拡張構文解析アルゴリズム   U A U G C U C C G C A C G A V CYKアルゴリズム C 学習アルゴリズム   RNA Sequence U 内側外側アルゴリズム RNA配列アラインメント、 RNA二次構造予測への応用 U A C C G G C U A Secondary Structure of RNA C G A RNA二次構造予測問題（基本バージョン）の定義   ベースペア B={{a,u},{g,c}｝ RNA二次構造    スコア関数    M={(i,j)|1≤i<j≤n,{ai,aj}∈B}、かつ i ≤h ≤j ≤k となる (ai,aj) ,(ah,ak) ∈M は無い μ(ai,aj)=1 if {ai,aj} ∈B μ(ai,aj)=0 otherwise 最適RNA二次構造  Σ(i,j)∈M μ(ai,aj) が最大となるM ベースペア a u g c 二次構造 agag cu agag cu RNA二次構造の表現 RNA二次構造予測のための動的計画法アルゴリズム   入力配列：a=a1…an アルゴリズム S (i, j )   S (i  1, j  1)   (ai, aj ) max max{ S (i, k  1)  S (k , j ) }   ik  j  j-1 j i+1 i 時間計算量テーブルのサイズO(n2)  1個のS(i,j)の計算O(n) ⇒ O(n3)時間  i k-1 k j 確率文脈自由文法とRNA二次構造の対応関係文法規則 X→ε X→a X→u X→g X→c X→YZ X→ a Y u X→ u Y a X→ g Y c X→ c Y g スコア Xのスコア 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 score(X)+score(Y) score(Y)+1 score(Y)+1 score(Y)+1 score(Y)+1 文法における生成規則と二次構造の対応 X→ a X→ YZ X→ a Y u Y a Z i k-1 k Y j a u 進化系統樹構成法  OHP参照タンパク質立体構造予測  神奈川科学技術アカデミー（KAST)講義資料参照遺伝子ネットワーク推定発現量ネットワーク遺伝子発現量の時間変化 ACETYL-CoA OXALOACETATE 推定 CIT2 MDH2 ACO1 MLS1 ISOCITRATE 時間 GLYOXYLATE ICL1 発現データからの遺伝子ネットワークの推定    環境変化（熱ショック、栄養状態）や発生、細胞分裂時の遺伝子の時系列データを観測時系列データから遺伝子の制御関係（ネットワーク）を推定解析にはクラスタリングが有効ネットワークモデル・推定手法       ブーリアンネットワーク微分方程式系（線形・非線形）ニューロ型モデル時系列解析ベイジアンネットワークグラフィカルモデリングブーリアンネットワーク同定  ブーリアンネットワーク   遺伝子制御ネットワークのモデル頂点⇔遺伝子、ブール関数⇔制御規則ブーリアンネットワーク同定   入出力パターンから一意に同定入次数が限定されていれば、O(log n)パターンから同定可能ブーリアンネットワークの例状態遷移表 A B 時刻ｔ C A’ = B B’ = A and C C’ = not A A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 時刻ｔ＋１ A’ 0 0 1 1 0 0 1 1 B’ 0 0 0 0 0 1 0 1 C’ 1 1 1 1 0 0 0 0 ブーリアンネットワークの同定    時刻 t, t+1 の状態の組（遷移表の一部） ⇒ 例例に無矛盾なネットーワークが一意かを判定例は発現パターンの変化に相当時刻ｔ A B C 1 0 0 0 1 0 0 1 1 時刻ｔ＋１ A’ 0 0 1 B’ 0 1 0 C’ 1 1 0 A’ = C B’ = B and (not C) C’ = not C A’ = C B’ = B xor C C’ = not C 入次数   ネットワーク形状に制約が無い場合 ⇒状態遷移表の全部の行（ 2n ）行が必要入次数が定数 K 以下 ⇒O(log n)行で十分入次数＝２ A 入次数＝３ A 理論的結果  状態遷移表の中からランダムに選んだ O(22 K  (2K   )  logn) 個の行が与え 1 られれば、確率 1  以上で n 与えられた例に無矛盾な入次数限定のブーリアンネットワークが一意に定まる。ブーリアンネットワーク同定に関する結果  少数の遺伝子の発現パターンのみが変化 ⇒多くの発現パターンが必要 ( (n K ) )  多数の遺伝子の発現パターンが変化 ⇒少ない発現パターンで十分 ( (log n) )  具体例パターン数： 100億個 vs 数百個バイオインフォマティクスの今後の課題     細胞や生物のシミュレーションタンパク質間相互作用、遺伝子間相互作用の推定個人差、種間の差の解析（配列の違いと形質の違いの関係の解明）医療、薬学への応用レポート課題  以下のいずれかを選択し、A4用紙で３ページ以上のレポートにして提出。なお、講義の感想や改善すべき点などもあれば書いて欲しい。     講義で述べたアルゴリズムのいずれかを実装し、実データに対して適用し、結果について考察せよ（プログラムのソースコードを添付すること）。５個以上の異なる種からの同じ種類のタンパク質データ（アミノ酸配列）のマルチプルアラインメントおよび進化系統樹を求め、さらに、結果について考察せよ。提出先：数理科学研究院事務室提出期限：１２月１０日