EECS500 Spring 2015 Department Colloquium

T.M. Murali
Signaling Hypergraphs
Virginia Tech
White 411
March 26, 2014

Cells communicate with each other to perform their functions within the body.  When a cell receives an external signal from the environment, it responds with a series of molecular reactions that alters the cell's behavior, e.g., causing it to divide, move, or self-destruct.  These reactions constitute networks called "signaling pathways" whose alterations can cause diseases such as cancers. Directed graphs are the most common representation of signaling pathways, making them amenable to a wide array of graph-theoretic algorithms. In this talk, I argue that directed graphs are inaccurate representations of the underlying biology of signaling reactions.  I describe an alternative mathematical representation called the "signaling hypergraph."  First, I illustrate how signaling hypergraphs overcome many limitations of graph-based representations. Second, I present a mixed integer linear program to solve the NP-hard shortest hyperpath problem.  Finally, I apply the algorithm to a well-known signaling pathway, and describe how the shortest hyperpaths better represent signaling reactions than the corresponding shortest paths in graphs.  I conclude with a summary of our ongoing research. Signaling hypergraphs exemplify how careful attention to the underlying biology can drive developments in a largely unexplored field of computer science.


T. M. Murali is an associate professor in the Department of Computer Science at Virginia Tech. He co-directs the ICTAS Center for Systems Biology of Engineered Tissues and is the associate director for the Computational Tissue Engineering interdisciplinary graduate education program. Murali's research group develops phenomenological and predictive models dealing with the function, behaviour, and properties of large-scale molecular interaction networks in the cell. He received his undergraduate degree in computer science from the Indian Institute of Technology, Madras and his Sc. M. and Ph. D. degrees from Brown University. Murali is an ACM Distinguished Scientist.  His group won the best paper award at the 2012 ACM Conference on Bioinformatics, Computational Biology, and Biomedicine.