Fast Sampling Algorithms for Identifying Pathway Occlusions in Metabolism

Abstract

Identifying metabolic pathways can provide valuable insights into underlying biochemical and metabolic stress, help discover novel drug targets, and enable the identification of metabolic biomarkers for early diagnosis and disease monitoring. In this project, we focus on identifying pathway occlusions in metabolism.

The problem is formulated as a mathematical model on a graph: Given a directed graph G = (V, E), where the vertex set V is known but the edge set E is governed by a probabilistic function, how can one efficiently recover the graph’s structure? At any given time, we can measure the connectivity strength of a vertex i ∈ V.

We begin with a special case where the presence of an edge between any pair of vertices is deterministic—each edge is either always present (with probability 1) or always absent (with probability 0). The objective is to reconstruct the graph’s edges based on the collected connectivity strength information.

We show that the solution to the connectivity matrix is not unique. Additionally, we demonstrate that a brute-force approach limits the graph size to four vertices on a classical computer. To overcome the limitations of brute force, we design both a Monte Carlo sampling algorithm and a randomized algorithm to reconstruct the graph’s edge set. These algorithms can handle graphs with hundreds of vertices. The probability of obtaining correct solutions is bounded using the Chernoff bound.

As future work, we aim to develop quantum sampling algorithms capable of scaling to even larger graphs.