Computer and Information Science and Engineering 

Extracellular molecules trigger a response inside the cell by initiating a signal at special membrane receptors (i.e., sources) which is then transmitted to transcription factors (i.e., targets) through various chains of interactions among proteins. Signaling networks describe this process. Understanding whether such a signal can reach from membrane receptors to transcription factors is essential in studying cell response and functions. This problem is drastically complicated due to the unreliability of the interaction data that are currently available. In this paper, we address this problem. More specifically, we develop a novel method that precisely computes the probability that a signal can reach from a given collection of receptors to a given collection of transcription factors when the underlying signaling network is uncertain. We do this by modeling the signaling networks as probabilistic networks. Our method represents each uncertain interaction as a bivariate polynomial. It transforms the reachability problem to a polynomial multiplication problem. In order to reduce the size of the resulting polynomials, we introduce novel polynomial collapsing operators that associate polynomial terms with possible paths between sources and targets as well as the cuts that separate sources from targets. Our experimental results on real and semi-synthetic signaling networks demonstrate orders of magnitude of improvement in terms of the running time over the state of the art methods that can precisely solve the same problem. We also demonstrate that this method can be used to find key associations between source and target genes in signaling networks.