Colloquia, Seminars and Conference News
Title : Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs
Date : April 7, 2006. (2:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Bhaskar DasGupta
Abstract:
In this talk 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.
Special cases of TR_p has been investigated
before in different contexts; the best previous results are
as follows:
(1) The minimum equivalent digraph problem,
that correspond to a special case of TR_1 with no critical edges,
is known to be MAX-SNP-hard, admits a polynomial time
algorithm with an approximation ratio of
1.617+c for any constant c>0 and
can be solved in linear time for directed acyclic graphs.
(2) A 2-approximation algorithm exists for TR_1.
In this talk, we will discuss the following results:
(a) We observe that TR_p, for any integer
p>0, can be solved in linear time
for directed acyclic graphs using the ideas used by previous researchers.
(b) We provide a 1.78-approximation
for TR_1 that improves the 2-approximation
mentioned in (2) above.
(c) We provide a 2+o(1)-approximation for TR_p on general graphs
for any prime p>0.
We will also discuss some ongoing research works in this direction
if time permits.
(These are joint result with Reka Albert, Riccardo Dondi and Eduardo Sontag)
Bio:
Bhaskar DasGupta is an associate professor in the Computer Science department at University of
Illinois at Chicago (UIC) and also affiliated with the Bioengineering department at UIC.
He did his PhD from University of Minnesota in 1995, was a post-doctoral fellow at DIMACS and jointly
at University of Waterloo and McMaster University in Canada before he joined the computer science
department of camden campus of Rutgers University; in 2001 he moved to UIC.
His research specific research interests include application of combinatorial/geometric techniques
to design efficient algorithms for computational problems in bioinformatics, systems biology and
hybrid systems; his broader research interests include designing efficient combinatorial algorithms
for computationally hard problems.
His research works have been supported by numerous NSF grants, including an NSF CAREER award.
[Back]
