Inference of pathways from metabolic networks by subgraph extraction

In this work, we present different algorithmic approaches to the inference of metabolic pathways from metabolic networks. Metabolic pathway inference can be applied to uncover the biological function of sets of co-expressed, enzyme-coding genes. We compare the kWalks algorithm based on random walks and an alternative approach relying on k-shortest paths. We study the influence of various parameters on the pathway inference accuracy, which we measure on a set of 71 reference metabolic pathways. The results illustrate that kWalks is significantly faster and has a higher sensitivity but the positive predictive value is better for the pair-wise k-shortest path algorithm. This finding motivated the design of a hybrid approach, which reaches an average accuracy of 72% for the given set of reference pathways.