A single source k-shortest paths algorithm to infer regulatory pathways in a gene network

Abstract

Motivation: Inferring the underlying regulatory pathways within a gene interaction network is a fundamental problem in Systems Biology to help understand the complex interactions and the regulation and flow of information within a system-of-interest. Given a weighted gene network and a gene in this network, the goal of an inference algorithm is to identify the potential regulatory pathways passing through this gene.

Results: In a departure from previous approaches that largely rely on the random walk model, we propose a novel single-source k-shortest paths based algorithm to address this inference problem. An important element of our approach is to explicitly account for and enhance the diversity of paths discovered by our algorithm. The intuition here is that diversity in paths can help enrich different functions and thereby better position one to understand the underlying system-of-interest. Results on the yeast gene network demonstrate the utility of the proposed approach over extant state-of-the-art inference algorithms. Beyond utility, our algorithm achieves a significant speedup over these baselines.

Availability: All data and codes are freely available upon request.

Fig. 1.

Two problems of the random walk model. (a) Normalization of edge weights is lossy. (b) The walks repeatedly go through the bidirectional edge

Fig. 2.

A graph and its corresponding pseudo tree. k=3. The node with a dash circle is a dummy node

Fig. 3.

An example with O(n²k) dummy nodes. (a) The graph. Each bold arrow represents k−1 paths. (b) The pseudo tree. The red box contains total (k−1)q dummy nodes in the paths from S to A_q−1

Fig. 4.

Overview of our inference framework

Fig. 5.

Evaluation using GO_ann: (a/b) The sorted e-values of the top GO term. (a) UnknownCausal using different k, (b) UnknownTarget using different k. The information model uses α=0.99. (c) The sorted maximal differences of e-values in each gold standard in UnknownTarget between the shortest paths and the diverse short paths using different λ. k=5

Fig. 6.

Evaluation using GO_all. (a) UnknownCausal using different k, (b) UnknownTarget using different k and (c) Maximal differences. The description is the same as Figure 5

Fig. 7.

The comparison between our algorithm and Y-STATISTICAL on our yeast gene network. The starting node is GGC1. k = 5. (a) The average importance value vs. the average k-paths diversity and (b) Execution time vs. the average k-paths diversity

Fig. 8.

The top 10 genes when λ = 0 and their main pathways, given the starting node RTS1. The weight of each edge is reported by its thickness. Darker nodes have higher importance values when λ = 1.0. k=5