NETSYNTHESIS: 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
pseudovertices 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)
pseudovertex collapse subject to the constraints that real (known)
vertices are not eliminated.
Some relevant publications

Réka Albert, Bhaskar DasGupta, Anthony Gitter, Gamze Gürsoy, Rashmi Hegde, Pradyut Pal, Gowri Sangeetha Sivanathan and Eduardo Sontag, A New Computationally Efficient Measure of Topological Redundancy of Biological and Social Networks, Physical Review E, 84 (3), 036117, 2011.
It is wellknown that biological and social interaction networks have a varying degree of redundancy,
though a consensus of the precise cause of this is so far lacking. In this paper, we introduce a topological
redundancy measure for labeled directed networks that is formal,
computationally efficient and applicable to a variety of directed
networks such as cellular signaling, metabolic and social interaction networks. We demonstrate the computational efficiency of our measure
by computing its value and statistical significance on a number of biological and social networks with up to
several thousands of nodes and edges.
Our results suggest a number of interesting observations:

social networks are more redundant that their biological counterparts,

transcriptional networks are less redundant than signaling networks,

the topological redundancy of the C. elegans metabolic network is largely due to its
inclusion of currency metabolites, and

the redundancy of signaling networks is highly (negatively) correlated with the monotonicity
of their dynamics.

Réka Albert, Bhaskar DasGupta, Riccardo Dondi and Eduardo Sontag,
Inferring (Biological) Signal Transduction Networks via Transitive Reductions of
Directed Graphs,
Algorithmica,
51 (2), 129159, 2008.
In this paper
we consider the pary 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.78approximation
for TR_{1} that improves the 2approximation
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
,
14 (7), 927949, 2007
(extended abstract in
7th Workshop on Algorithms in Bioinformatics (WABI),
R. Giancarlo and S. Hannenhalli (Eds.), LNBI 4645,
SpringerVerlag, 407419, 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,
NETSYNTHESIS: A software for synthesis, inference and simplification of signal transduction networks,
Bioinformatics,
24 (2), 293295, 2008
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.
Softwarerelated links
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.