Estimating reachability in dense biological networks

Biological networks provide a holistic view for modeling and analysis of interactions among various kinds of gene products. Finding whether a signal can successfully arrive at a target gene from a given source gene is one of the key problems on biological networks. This is also known as the reachability problem. Computing the probability of signal reachability is a #P-complete problem. This complexity stems from the inherent uncertainty of the interactions. Existing methods fail to scale to large and dense networks. In this paper, we develop a novel method to estimate the reachability probability in probabilistic biological networks. We develop a general theory for utilizing Monte Carlo sampling to solve this problem with a mathematically proven confidence bound on the result. We present three alternative sampling approaches which follow our theory. We experimentally validate our theory, and compare the performance of our method with the state of the art PReach method. We finally use our method to analyze reachability in cell growth and death pathways in different cancer types, which was impossible using existing methods due to the large scale of the networks.