九州大学大学院 情報学専攻特別講義 （９） ブーリアンネットワークの 解析と制御

Presentation on theme: "九州大学大学院 情報学専攻特別講義 （９） ブーリアンネットワークの 解析と制御"— Presentation transcript:

1 九州大学大学院 情報学専攻特別講義 （９） ブーリアンネットワークの 解析と制御
九州大学大学院　情報学専攻特別講義 （９） ブーリアンネットワークの 解析と制御 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義内容 バイオインフォマティクス概論（資料なし） 配列アラインメント 配列解析 RNA二次構造予測 タンパク質立体構造の比較と予測
固定パラメータアルゴリズムと部分k木 グラフの比較と列挙 ニューラルネットワークの離散モデル ブーリアンネットワークの解析と制御 講義の進展状況によっては内容に変更の可能性あり

3 ブーリアンネットワークの 解析と制御

4 講義内容 ブーリアンネットワーク アトラクター検出問題 アトラクター検出アルゴリズム ブーリアンネットワークの制御 アトラクターの観測

5 ブーリアンネットワーク

6 ブーリアンネットワーク 遺伝子ネットワークの数理モデル 頂点⇔遺伝子 制御規則 状態は（クロックに）同期して変化
状態：　1 (発現) と 0 (非発現)のみ 制御規則 ブール関数 (AND, OR, NOT …) もし、y が x を直接制御していれば、y から x に辺が存在 状態は（クロックに）同期して変化 基本的にデジタル回路と同じ [Kauffman: Nature, 224:177–178, 1969]

7 ブーリアンネットワークの例 A B C ブーリアンネットワーク 状態遷移表 ’ = B ’ = A and C ’ = not A A
time ｔ ｔ＋１ B C 1 INPUT OUTPUT 状態変化の例： １１１　⇒　１１０　⇒　１００　⇒　０００　⇒　００１　⇒　００１　⇒　００１　⇒　。。。

8 状態遷移ダイアグラム 状態遷移表 状態遷移ダイアグラム A ’ B’ C’ B C 1 time INPUT OUTPUT 000 010
ｔ ｔ＋１ B C 1 INPUT OUTPUT 000 010 001 101 100 110 011 111 状態遷移表 状態遷移ダイアグラム

9 アトラクター検出問題

10 アトラクター 定常状態 細胞の種類に対応？ 例 点アトラクター：１つの状態だけ 周期的アトラクター：複数の状態からなる
011 ⇒ 101 ⇒ 010 ⇒ 101 ⇒ 010 ⇒… 111 ⇒ 110 ⇒ 100 ⇒ 000 ⇒ 001 ⇒ 001 ⇒　001 ⇒ … 点アトラクター：１つの状態だけ 周期的アトラクター：複数の状態からなる 000 010 001 101 100 110 011 111 周期的アトラクター 点アトラクター

11 アトラクター検出についての背景 ブーリアンネットワーク（BN）の状態数が 2n なので、妥当なブール関数からなるBNの場合、 時間で解ける しかし、n が大きいと計算が困難 様々なヒューリスティック法があるが、理論的保証がない [Irons: Pysica D, 2006], [Devloo et al.: Bull. Math. Biol. 2003], … 点アトラクターの検出はNP困難、さらに、点アトラクターの数え上げは#P困難　[Akutsu et al.: GIW 1998] O*(f(n)) は O(f(n) poly(n))　を表す

12 点アトラクター attractor

13 アトラクター検出 アルゴリズム

14 点アトラクター検出のSAT（論理式充足問題）への変換
最大入次数が K の場合、 (K+1)-SATに変換可能 (Boolean SATisfiability problem) vj vk vi

15 AND/OR BNに対するO(1.587n) 時間アルゴリズム（１）
AND/OR BN:　各頂点は literal の AND もしくは OR 関数 （ただし、入次数の制約はなし） K+1 SAT への変換は有用でない（ K が定数でない） 方法: 再帰的に各頂点への0-1割り当てを行う [Melkman, Tamura, Akutsu: IPL 2010]

16 AND/OR BNに対するO(1.587n) 時間アルゴリズム（２）
f(k) を k 頂点からなるBNに対する 0-1割り当ての個数とすると この漸化式 (Fibonacci数の式に類似)を解くと, f(k) は O(1.4656k) しかし、この方法を継続するには３頂点からなるパスが必要。それがなくなった時点で SAT のアルゴリズムを利用（詳細は省略） 　　⇒ O(1.587n) 時間アルゴリズム

17 点アトラクターの再帰的数え上げアルゴリズム (1)
頂点への0-1割り当てを再帰的に試行 点アトラクターにならないことがわかったらバックトラック [Zhang et al.: EURASIP JBSB 2007]

18 点アトラクターの再帰的数え上げアルゴリズム (2)
0-1割り当てを順に拡張していき、点アトラクターにならないことがわかったらバックトラックする 00 　Ｘ　 　backtrack 01 010　 　Ｘ　 　backtrack 011　 　Ｘ　 　backtrack 10 平均計算量は以下の表のとおり（K: 最大入次数） 単純な O*(2n) 時間アルゴリズムより、はるかに高速 K 2 3 4 5 6 Complexity 1.35n 1.43n 1.49n 1.53n 1.57n

19 再帰的アルゴリズムの実行の様子 1 1 1 Output

20 v1 vm-1 vm vm+1 t=0 t=1 平均時間計算量の解析 K
最初のm個の頂点まで0-1割り当てが行われた時に、vi(0)≠vi(1) が検出される確率は m 個の頂点に対するランダムな0-1割り当てが点アトラクターに対応する可能性がある確率は よって、m個の頂点への0-1割り当てのうち点アトラクターになる可能性のあるものの個数は １からnまでの m に対して、上式の最大値を計算 v1 vm-1 vm vm+1 t=0 t=1 K

21 ブーリアンネットワークの制御

22 ブーリアンネットワークの制御モデル 入力 出力 内部頂点： v1 ,…, vn , 制御頂点： u1 ,…, um
初期状態： v0 　　　　　　目標状態： vM 　　　　　ブーリアンネットワーク 出力 以下を満たす制御頂点の状態系列：　u(0), u(1), …, u(M) v(0)=v0, v(M)=vM 　　　（時刻０で初期状態、時刻Ｍで目標状態） [Akutsu et al., J. Theo. Biol. 2007]

23 ブーリアンネットワークの制御 木構造なら多項式時間で解ける それ以外だと、かなりの制約を与えてもNP困難
他の手法 SAT（充足問題性判定問題）の利用 [Langmead & Jha, JBCB, 2009] 整数計画法の利用 [Akutsu et al., IEEE CDC 2009][Kobayashi & Hiraishi, Automatica, 2011] セミテンソル解析の利用 [Cheng & Qi, Automatica 2009]

24 動的計画法アルゴリズム（１） PBN版（Datta et al., 2003）を簡単化 DPテーブル:
時刻 t における n個の遺伝子の状態が b1,…,bnの時、目標状態に至る制御系列があれば１、それ以外は０

25 動的計画法アルゴリズム（２） D[1,1,1, 2] =1 D[0,0,0, 2] = 0 D[0,1,1, 3] = 1
u1=1, u2=1 DP Computation D[0,1,1, 3] = 1 問題点： テーブルのサイズ が指数オーダー ⇒ NP困難なので 仕方がない

26 アトラクターの観測 [Hou, Tamura, Ching, Akutsu: Automatica 2017]

27 可観測性 可観測性: 制御理論において重要、可制御性の双対
システムが可観測 ⇔ 過去のシステム全体の状態を（適切な制御を与えて）いくつかの頂点の時系列データのみから推定可能 しかし、ブーリアンネットワークではO(n)個の頂点を観測することが必要になる場合があり、非現実的 解決策の一つ: 定常状態（細胞の種類）のみを少数の遺伝子の発現データから同定 　　⇒動的バイオマーカー検出

28 動的バイオマーカー検出 入力： BNにおける定常状態（細胞の種類に対応） 出力： それらを区別可能な最小個数の遺伝子セット
出力：　それらを区別可能な最小個数の遺伝子セット 定理：　２個の動的定常状態は、２個の遺伝子のみを観測することで区別可能 [Cheng et al.: Automatica, 84: , 2017]

29 中国剰余定理 孫子算経（３～５世紀）： ある数を3で割ると2余り、5で割ると3余り、7で割ると2余るという。その数は何か？ 中国剰余定理
孫子算経（３～５世紀）：　ある数を3で割ると2余り、5で割ると3余り、7で割ると2余るという。その数は何か？ 中国剰余定理 正整数 m1,…,mt が互いに素とすると、 は、[0, m1m2… mt-1]の中にただ一つの解を持つ

30 証明の概略 定理： ２個の動的定常状態は、２個の遺伝子のみを観測することで区別可能 対偶を証明 どの２個をとっても周期を持つ（区別不能）
定理：　２個の動的定常状態は、２個の遺伝子のみを観測することで区別可能 対偶を証明 どの２個をとっても周期を持つ（区別不能） ⇒上の命題（中国剰余定理の拡張版）より、全体に対する周期解が存在 ⇒２個の定常状態は同じ

31 結論

32 まとめ ブーリアンネットワーク アトラクターの検出 ブーリアンネットワークの制御 アトラクターの観測 参考文献（その他の結果）
遺伝子ネットワークの離散数理モデル 1969に提案された古いモデルだが、今でも多くの研究 アトラクターの検出 NP困難 入次数がK以下の場合、 (K+1)-SAT に帰着可能 AND/OR 関数だけからなるBNの場合、 O(1.587n) 時間で解ける ブーリアンネットワークの制御 動的計画法で解ける（ただし、指数オーダーの計算量） アトラクターの観測 ２個の周期的アトラクターは２個の遺伝子（頂点）の観測により区別可能 （<=中国剰余定理) 参考文献（その他の結果） T. Akutsu: Algorithms for Analysis, Inference, and Control of Boolean Networks, World Scientific, 2018