MARKOV CHAIN MONTE CARLO METHODS TO ANALYZE THE STEADY-STATE FLUX SOLUTION SPACE OF METABOLIC NETWORK MODELS

摘要

The steady-state flux solution space of a metabolic network model represents a convex polytope. Determining the size and shape of the flux solution space can give valuable information for a better understanding of the fluxes operating metabolic processes within living cells. For realistic problems, the polytope is usually high dimensional. Computing its volume analytically is proven to be #P-hard (Dyer and Frieze 1998). Therefore, Monte Carlo methods are used to approximate the volume numerically. To cope with high-dimensional problems (＞ 20 dimensions), naive Monte Carlo approaches, however, generally fail. We propose a new Markov Chain Monte Carlo method in combination with a Hit and Run algorithm that is able to cope with the volume estimation problem in high dimensions. Based on quantitative measures we analyze the performance of our algorithm. By application to an example metabolic network model of realistic size we could demonstrate reasonable running times even without taking paral-lelization into account. The results show that Markov Chain methods are capable to analyze the size and shape of flux solution spaces for large-scale network models. Thus, flux space volume estimation has the potential to become a new member of the computational toolset for constraint based modeling.