Title: Synthesizing and Minimizing Signal Transduction (and Social) Networks
Speaker: Bhaskar DasGupta, University of Illinois at Chicago
Date: Monday, October 6, 2008 12:00 - 1:30 pm
Location: DyDAn Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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:
(a) 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. The transitive reduction approach is also useful in the context of sparsifying social networks such as the ENRON email network.
(b) 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. Time permitting, I will also discuss how we used this methodology to synthesize and simplify a novel network corresponding to activation induced cell death in large granular lymphocyte leukemia.
The corresponding software NET-SYNTHESIS is freely downloadable from http://www.cs.uic.edu/~dasgupta/network-synthesis/
(Joint work with various subsets of the following authors: R. Albert, P. Berman, R. Dondi, S. Kachalo, M. Karpinski, E. Sontag, A. Zelikovsky, K. Westbrooks and R. Zhang)
See our new DIMACS/DyDAn Multidisciplinary Seminar Series
Back to DyDAn Home Page
Back to DIMACS Home Page