DIMACS TR: 2005-41
Inferring (Biological) Signal Transduction Networks via Binary Transitive Reductions
Authors: Reka Albert, Bhaskar DasGupta, Riccardo Dondi and Eduardo Sontag
ABSTRACT
In this paper we consider the binary transitive reduction (BTR) problem that
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. Special cases of BTR has been investigated
before in different contexts; the best previous results are as follows:
(1) the minimum equivalent digraph problem,
that correspond to the special case of BTR with no critical edges and
all edges labels being zeroes, is known to be MAX-SNP-hard, admits a polynomial time
algorithm with an approximation ratio of
1.617 + \epsilon for any constant \epsilin > 0 and
can be solved in linear time for directed acyclic graphs.
(2) a 2-approximation algorithm exists for the special case of BTR in which all edge labels
are zeroes.
In this paper, our contributions include:
-- observing that the BTR problem can be solved in linear time for directed acyclic graphs,
-- providing a 1.78-approximation for the restricted version of BTR when all edge labels
are zeroes (the same restricted version as in (2) above), and
-- providing a $2+o(1)$-approximation for BTR on general graphs.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-41.ps.gz
DIMACS Home Page