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

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

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

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

ブーリアンネットワーク

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

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

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

アトラクター検出問題

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

アトラクター検出についての背景 ブーリアンネットワーク（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))　を表す

点アトラクター attractor

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

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

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

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

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

点アトラクターの再帰的数え上げアルゴリズム (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

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

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

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

ブーリアンネットワークの制御モデル 入力 出力 内部頂点： 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]

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

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

動的計画法アルゴリズム（２） 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困難なので 仕方がない

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

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

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

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

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

結論

まとめ ブーリアンネットワーク アトラクターの検出 ブーリアンネットワークの制御 アトラクターの観測 参考文献（その他の結果） 遺伝子ネットワークの離散数理モデル 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