Accurate metabolic flux analysis (MFA) is of great importance in analyzing cell physiology and evaluating cellular mechanisms. Currently, the most popular MFA methods make use of external flux and isotopic measurements to find the set of intracellular fluxes that minimizes the difference between observed and simulated measurements. A key question is whether the set of measured fluxes yield a unique of flux distribution upon elucidation. This identifiability problem in MFA with isotopic considerations is difficult since isotopic balances yield nonlinear constraints. The problem and its difficulty have been recognized for more than a decade, and several theoretical and computational approaches have been proposed to address this problem. However, there has been no previous work of determining the smallest (and most cost effective) set of measurements that lead to complete flux elucidation.

In this paper, we employ an integer programming (IP) framework for the mathematical analysis of metabolic pathways to answer this question. The proposed framework utilizes structural analysis that has been extensively used in the control community. Structural analysis is directly related to the generic rank of a structural matrix. In the proposed framework, a mathematical programming approach is used that connects the identification of the generic rank problem to the output set assignment problem. In this approach, one assigns each variable (flux or isotopic distribution) that needs to be determined as an output variable to an equation (flux balance or isotopic balance). Each equation can have only one output variable. Therefore, if all the quantities but the output variable in an equation are known, then the output variable is the only unknown in the equation, and can be determined by solving the equation. All the unassigned variables need to be determined by proper measurements experiments. This approach results in an integer linear programming formulation while accounting for the case of partial measurements (e.g., when only some fragments are measured). The proposed framework has been tested on well-studied small demonstration examples. We subsequently benchmark the proposed framework by applying it to recently published medium- and large-scale metabolic networks of Escherichia coli to exhaustively identify all measurements options. Both theoretical and computational results will be presented.