Middle East Technical University, Ankara.
IEEE/ACM Trans Comput Biol Bioinform. 2013 Jul-Aug;10(4):869-83. doi: 10.1109/TCBB.2013.80.
Inference of topology of signaling networks from perturbation experiments is a challenging problem. Recently, the inference problem has been formulated as a reference network editing problem and it has been shown that finding the minimum number of edit operations on a reference network to comply with perturbation experiments is an NP-complete problem. In this paper, we propose an integer linear optimization (ILP) model for reconstruction of signaling networks from RNAi data and a reference network. The ILP model guarantees the optimal solution; however, is practical only for small signaling networks of size 10-15 genes due to computational complexity. To scale for large signaling networks, we propose a divide and conquer-based heuristic, in which a given reference network is divided into smaller subnetworks that are solved separately and the solutions are merged together to form the solution for the large network. We validate our proposed approach on real and synthetic data sets, and comparison with the state of the art shows that our proposed approach is able to scale better for large networks while attaining similar or better biological accuracy.
从扰动实验推断信号网络的拓扑结构是一个具有挑战性的问题。最近，该推断问题已被表述为参考网络编辑问题，并且已经表明，找到符合扰动实验的参考网络上的最小编辑操作数是一个 NP 完全问题。在本文中，我们提出了一种基于整数线性优化 (ILP) 的模型，用于从 RNAi 数据和参考网络中重建信号网络。ILP 模型保证了最优解；然而，由于计算复杂性，仅适用于大小为 10-15 个基因的小型信号网络。为了扩展到大型信号网络，我们提出了一种基于分治的启发式方法，其中将给定的参考网络划分为较小的子网，分别求解，并将解决方案合并形成大型网络的解决方案。我们在真实和合成数据集上验证了我们提出的方法，与现有技术的比较表明，我们提出的方法能够更好地扩展到大型网络，同时获得相似或更好的生物学准确性。
