The University of Arizona

Events & News

CS Colloquium

DateThursday, November 20, 2014
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 11am in Gould-Simpson 906.

Faculty Host: John Kececioglu
SpeakerAnna Ritz
AffiliationVirginia Tech

Signaling Hypergraphs

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. Signaling hypergraphs
exemplify how careful attention to the underlying biology can drive
developments in a largely unexplored field of computer science.


Anna Ritz is a postdoctoral research associate in T. M. Murali's group
at Virginia Tech. She obtained her Ph.D. and Sc.M. in Computer Science
from Brown University, where she was awarded a National Science
Foundation Graduate Research Fellowship. She received a B.A. in
Computer Science at Carleton College. Dr. Ritz's postdoctoral
research areas involve analyzing and modeling human signaling
pathways, from automatically reconstructing pathways to developing
alternative mathematical representations of signaling events. Her
postdoctoral work is a departure from her Ph.D. research, where she
studied structural variation in human genomes using single-molecule
``third-generation'' sequencing technologies.