9/9 – Anthony Gitter, University of Wiscousin – Madison

Abstract: We present an algorithm that uses constraint-solving techniques first developed in the context of formal verification to explore pathways in a biological network. Biological pathways describe how groups of proteins cooperate to accomplish cellular activities, such as regulating cell growth. These pathways are often represented as signed directed graphs that depict protein-protein relationships. We present a method for automatically discovering pathway structures that explain how cells respond to outside stimuli. The Temporal Pathway Synthesizer algorithm takes as input a background network of candidate edges and experimental data measuring if and when nodes in the network respond to those changes. It generates signed directed graphs that explain how information propagates through the graph over time. The Temporal Pathway Synthesizer systematically eliminates all candidate structures for a signaling pathway in which a protein node is activated or inactivated before its upstream regulators. These temporal rules are combined with other discrete constraints derived from the graph topology or prior knowledge. Furthermore, we explore how our computationally-predicted pathways deviate from manually-curated pathways. We present preliminary ideas about how graph topological properties can be used to improve the ability to prioritize biological experiments with the predicted pathways.