単調なサブシステムへの生物学的ネットワークの分解のアルゴリズムと複雑さの結果

大規模な生物学的ネットワークの数学的分析への有用なアプローチは、単調な動的システムへの分解に基づいています。このペーパーでは、適切な意味で最適な分解を見つけることに関連する2つの計算上の問題を扱います。グラフ理論言語では、問題は最大の標識一貫性のあるサブグラフの観点からリキャストできます。理論的な結果には、多項式時間近似アルゴリズムと一定の比較の近似可能性の結果が含まれます。最適性から87.9％の最悪の保証を持つアルゴリズムの1つは、Goemans-Williamsonのセミフィニットプログラミングリラクゼーションアプローチに基づいています[Goemans、M.、Williamson、D.、1995。セミディナイトプログラミングを使用した満足度の問題。J. ACM 42（6）、1115-1145]。アルゴリズムは、ショウジョウバエセグメンテーションネットワークと表皮成長因子受容体経路モデルで実装およびテストされ、最適に実行することがわかった。

A useful approach to the mathematical analysis of large-scale biological networks is based upon their decompositions into monotone dynamical systems. This paper deals with two computational problems associated to finding decompositions which are optimal in an appropriate sense. In graph-theoretic language, the problems can be recast in terms of maximal sign-consistent subgraphs. The theoretical results include polynomial-time approximation algorithms as well as constant-ratio inapproximability results. One of the algorithms, which has a worst-case guarantee of 87.9% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson [Goemans, M., Williamson, D., 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (6), 1115-1145]. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model, and it was found to perform close to optimally.