A Divide and Conquer Approach for Construction of Large-Scale Signaling Networks from PPI and RNAi Data Using Linear Programming

2013-07-01
Ozsoy, Oyku Eren
Can, Tolga
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.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS

Suggestions

AN OPTIMAL-CONTROL PROBLEM WITH NONLINEAR ELLIPTIC STATE-EQUATIONS
Leblebicioğlu, Mehmet Kemal (Elsevier BV, 1992-02-01)
In this article some of the results for optimal control of linear systems have been generalized to a nonlinear case. This is achieved by employing standard techniques of the nonlinear theory. After demonstrating the existence of optimal controls, finite element method is used to discretize the problem. The resulting finite dimensional problem is solved by a special algorithm. The theoretical discussions are completed by proving that approximate solutions are reduced to exact solutions as the element size te...
A strange recursion operator for a new integrable system of coupled Korteweg-de Vries equations
Karasu, A; Karasu, Atalay; Sakovich, SY (Springer Science and Business Media LLC, 2004-08-01)
A recursion operator is constructed for a new integrable system of coupled Korteweg de Vries equations by the method of gauge-invariant description of zero-curvature representations. This second-order recursion operator is characterized by unusual structure of its nonlocal part.
A model for the computation of quantum billiards with arbitrary shapes
Erhan, Inci M.; Taşeli, Hasan (Elsevier BV, 2006-10-01)
An expansion method for the stationary Schrodinger equation of a three-dimensional quantum billiard system whose boundary is defined by an arbitrary analytic function is introduced. The method is based on a coordinate transformation and an expansion in spherical harmonics. The effectiveness is verified and confirmed by a numerical example, which is a billiard system depending on a parameter.
A nested iterative scheme for computation of incompressible flows in long domains
Manguoğlu, Murat; Tezduyar, Tayfun E.; Sathe, Sunil (Springer Science and Business Media LLC, 2008-12-01)
We present an effective preconditioning technique for solving the nonsymmetric linear systems encountered in computation of incompressible flows in long domains. The application category we focus on is arterial fluid mechanics. These linear systems are solved using a nested iterative scheme with an outer Richardson scheme and an inner iteration that is handled via a Krylov subspace method. Test computations that demonstrate the robustness of our nested scheme are presented.
A finite element variational multiscale method for the Navier-Stokes equations
Volker, John; Kaya Merdan, Songül (Society for Industrial & Applied Mathematics (SIAM), 2005-01-01)
This paper presents a variational multiscale method (VMS) for the incompressible Navier-Stokes equations which is defined by a large scale space L-H for the velocity deformation tensor and a turbulent viscosity nu(T). The connection of this method to the standard formulation of a VMS is explained. The conditions on L-H under which the VMS can be implemented easily and efficiently into an existing finite element code for solving the Navier - Stokes equations are studied. Numerical tests with the Smagorinsky ...
Citation Formats
O. E. Ozsoy and T. Can, “A Divide and Conquer Approach for Construction of Large-Scale Signaling Networks from PPI and RNAi Data Using Linear Programming,” IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, pp. 869–883, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/37380.