DIMACS TR: 2005-41

Inferring (Biological) Signal Transduction Networks via Binary Transitive Reductions

Authors: Reka Albert, Bhaskar DasGupta, Riccardo Dondi and Eduardo Sontag


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