NET-SYNTHESIS: A software for synthesis, inference and simplification of signal transduction networks

Our software performs combined synthesis, inference and simplification of signal transduction networks. The main idea of the application lies in representing observed indirect causal relationships as network paths, introducing pseudo-vertices for unknown intermediaries of these paths and using techniques from combinatorial optimization to find the most parsimonious graph consistent with all experimental observations. The software contains algorithms for (i) transitive reduction of an initially synthesized graph subject to the constraints that no edges corresponding to direct interactions are eliminated and (ii) pseudo-vertex collapse subject to the constraints that real (known) vertices are not eliminated.

Some relevant publications

• Réka Albert, Bhaskar DasGupta, Riccardo Dondi and Eduardo Sontag, Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs, to appear in Algorithmica.
  
  In this paper we consider the p-ary transitive reduction (TR_p) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. In this paper, our contributions are as follows:
  • We observe that TR_p, for any integer p>0, can be solved in linear time for directed acyclic graphs.
  • We provide a 1.78-approximation for TR₁ that improves the 2-approximation known before.
  • We provide a 2+o(1)-approximation for TR_p on general graphs for any fixed prime p>1.
  
  
• Réka Albert, Bhaskar DasGupta, Riccardo Dondi, Sema Kachalo, Eduardo Sontag, Alexander Zelikovsky and Kelly Westbrook, A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence, Journal of Computational Biology , Volume 14, Number 7, pp. 927-949, 2007 (extended abstract in 7th Workshop on Algorithms in Bioinformatics (WABI), R. Giancarlo and S. Hannenhalli (Eds.), LNBI 4645, Springer-Verlag, pp. 407-419, September 2007).
  
  We introduce a new method of combined synthesis and inference of biological signal transduction networks. A main idea of our method lies in representing observed causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. Our contributions are twofold:
  • we formalize our approach, study its computational complexity and prove new results for exact and approximate solutions of the computationally hard transitive reduction substep of the approach;
  • we validate the biological usability of our approach by successfully applying it to a previously published signal transduction network by Li et al. and show that our algorithm for the transitive reduction substep performs well on graphs with a structure similar to those observed in transcriptional regulatory and signal transduction networks.
  
  
• Sema Kachalo, Ranran Zhang, Eduardo Sontag, Réka Albert and Bhaskar DasGupta, NET-SYNTHESIS: A software for synthesis, inference and simplification of signal transduction networks, Bioinformatics, Volume 24, Number 2, pp. 293-295, January 2008 (doi: 10.1093/bioinformatics/btm571).
  
  We present a software for combined synthesis, inference and simplification of signal transduction networks. The main idea of our method lies in representing observed indirect causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. We illustrate the biological usability of our software by applying it to a previously published signal transduction network and by using it to synthesize and simplify a novel network corresponding to activation induced cell death in large granular lymphocyte leukemia.

Software-related links

• drawgraph.exe (windows version; save and run on your local computer)
• Format for input file for network synthesis
• A sample input file to play with the software . The first few lines of the file provides a suggested sequence of actions.
• Brief explanation of the software (short manual).
• Detailed performance of the transitive reduction algorithm on some simulated biological networks.
• Synthesizing a real signal transduction network:
  • The network manually synthesized by Li et al. redrawn for easier visual comparison.
  • The network synthesized by our software. A pseudo-node is displayed as ⊛

Copyright (C) 2006 Semen Kachalo. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.