Optimal Inference of Asynchronous Boolean Network Models

技術要約：非同期ブールネットワークの最適推論

問題提起
本論文は、実験データから遺伝子制御ネットワーク（GRN）を推論する際の課題、特にブールネットワーク（BN）モデルの再構築に焦点を当てている。核心となる困難は「次元の呪い」であり、探索可能なネットワークの空間は遺伝子数とともに指数関数的に増大するため、推論が過学習に対して脆弱になる。既存の手法は実験ノイズをモデル化するために確率論に依存することが多いが、著者らは、生物学的ネットワークは複雑な計算メカニズムを表現しており、連続する時点間の依存関係は高度に非線形であり、測定ノイズよりも多くの変動をもたらすことが多いと主張している。

さらに、シングルセルRNA-Seq（scRNA-seq）データ特有の課題が生じる。すなわち、測定値は細胞状態の経時的な進行を表しているものの、データセットには固有の時系列順序（擬似時間）がない「スナップショット」しか存在しない。現在の手法は、ネットワーク構造、論理関数、およびこれらスナップショットの正しい時間的順序を同時に推論することに苦慮している。特に、ネットワークのダイナミクスが非同期（非決定論的）である場合に顕著である。

手法
著者らは、最適なブールネットワークモデルを推論するために、アルゴリズム情報理論（具体的にはコルモゴロフ複雑性）に基づいた新しいフレームワークを提案している。中心となる前提は、最適なモデルとは、ネットワークの符号化長と「ノイズビット」（モデルの出力と観測データの間の不一致）の合計を最小化するものであるという点である。

• 目的関数: $\nu + \epsilon$ を最小化することを目標とする。ここで $\nu$ はノイズビット（不一致）の数であり、$\epsilon$ はネットワークの符号化長である。符号化長は、レギュレーター（調節因子）や論理関数を置換することによって形成され得るネットワークの数の底数2（$\log_2$）として計算される。このアプローチは、多くのパラメータを持つ複雑なモデルにペナルティを課し、データをよく説明するより単純な説明を優先させる。
• 非同期性と非決定論の処理: 決定論的な従来のアプローチとは異なり、本研究は非決定論的な計算を扱うためのフレームワークを拡張している。著者らは、「遅延された変化」（遺伝子の状態がレギュレーターの現在の状態を即座に反映しない非同期更新）をノイズビットと同じコストとして扱うコストメカニズムを導入している。これにより、固定された更新順序を仮定することなく、非同期ダイナミクスを考慮したモデル化が可能になる。
• 整数線形計画法（ILP）による最適化: 推論問題は、0/1 整数線形計画問題として定式化される。
  • 変数: モデルは、不一致（$B$）、論理関数の出力（$I$）、レギュレーターの選択（$R$）、レギュレーターの数（$V$）、および非同期遷移（$D$）を表すバイナリ変数を使用する。
  • 制約条件: 制約条件は、論理関数が選択されたレギュレーターと整合していること、および非同期遷移（$D$）が、ステップ間で遺伝子の状態が変化しない場合にのみ許可されることを保証する。
  • ヒューリスティック（MEDSI）: この問題が（頂点被覆問題への帰着を通じて証明されたように）NP完全であることを踏まえ、著者らはMEDSI（Minimum Edit Distance from a State of Ignorance）と呼ばれるヒューリスティック探索アルゴリズムを導入している。このアルゴリズムは、大規模なデータセットにおける不整合を解決するために、クラスタリングと再帰的論理を使用しており、このアプローチのスケールアップを可能にしている。
• 擬似時間推論（TICO）: scRNA-seq データの時間的順序の欠如に対処するため、著者らはTICO（Timeless Inference of Cell Ordering）を提案している。この手順は、期待値最大化（EM）アルゴリズムと同様に機能する：
  1. 初期ネットワーク構造と論理から開始する。
  2. シミュレーションされた軌跡を生成し、観測された細胞状態をそれらの軌跡の最も近い点にマッピングすることで、擬似時間を割り当てる。
  3. 割り当てられた擬似時間を用いてネットワークを再構築する。
  4. 解のコスト（符号化長 + ノイズ）が収束するまで反復する。

主な貢献

1. アルゴリズム複雑性フレームワーク: 著者らは、ネットワーク推論に対する非確率論的アプローチを導入し、「最良の」モデルを、データを説明する最短の符号化に基づいて定義した。これにより、ランダムなノイズと複雑な計算ダイナミクスを効果的に区別している。
2. 非同期ブール推論: 本研究は、非同期および非決定論的なダイナミクスを明示的に考慮する、ブールネットワークを推論するための最適なアルゴリズムを提示している。これは、標準的なBN推論ではしばしば無視される特徴である。
3. 統合された擬似時間推論: TICO アルゴリズムにより、同一のアルゴリズム情報フレームワーク内で、ネットワーク構造とシングルセルの時間的順序を同時に推論することが可能になる。
4. スケーラブルなヒューリスティック: MEDSI ヒューリスティックの開発により、厳密な最適化基準を、正確な ILP 解が計算上困難となる可能性のある大規模なデータセットに適用することが可能になった。

結果
本手法は、3種類のデータセットで評価された。

• 実際の scRNA-seq データ: ヒト造血幹細胞データ（GSE75478）に適用された。推論されたネットワークを用いて TICO により細胞を順序付けたところ、文献由来の初期ネットワークと比較して、分化マーカー CD38 との相関が有意に高く（倍率変化 1.7 および 2.6）、p 値も低かった。
• シミュレーションネットワーク: 固定、均質、およびスケールフリーのトポロジーにおいて、様々なノイズレベルでのテストを行った結果、提案手法（MEDSI）は、BestFit、ATEN、CANTATA といった既存のツールよりも一貫して高い Matthews 相関係数（MCC）を達成した。著者らは、相関ベースの手法（BestFit など）は、明確な状態と低いノイズを持つスケールフリー・トポロジーでは良好に機能したが、他のトポロジーや高いノイズ条件下では失敗したと指摘している。
• 文献ネットワーク: Cho らの細胞周期モデルを用いたところ、本手法は 0.57 の MCC を達成し、偽のレギュレーターを正しく除外したが、競合するツールは -0.14 から 0.22 の範囲の MCC を示した。

意義と主張
著者らは、統計的な相関だけでなく、基礎となる計算メカニズムに焦点を当てることで、複雑な生物学的システムを推論するためのより堅牢なツールを提供すると主張している。彼らは、計算プロセスをモデル化することが、ネットワークのトポロジーやデータセットの特性によって相関ベースの手法が失敗するシナリオにおいて、より良い予測につながると断言している。本論文は、ノイズに関する確率的な仮定に依存せず、不一致をアルゴリズム複雑性の枠組みにおけるコストとして扱うことで、高スループットなデータセットに対して最適または準最適な解を見つけるための実行可能な経路として、提案された ILP 定式化とヒューリスティックを提示している。