発現データからのガン細胞分類

確率文脈自由文法と
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用紙で３ページ以
上のレポートにして提出。なお、講義の感想や改
善すべき点などもあれば書いて欲しい。




講義で述べたアルゴリズムのいずれかを実装し、実
データに対して適用し、結果について考察せよ（プロ
グラムのソースコードを添付すること）。
５個以上の異なる種からの同じ種類のタンパク質デー
タ（アミノ酸配列）のマルチプルアラインメントおよび進
化系統樹を求め、さらに、結果について考察せよ。
提出先：数理科学研究院事務室
提出期限：１２月１０日

Download Report