Obstructions to Sampling Qualitative Properties

Abstract

Background: Sampling methods have proven to be a very efficient and intuitive method to understand properties of complicated spaces that cannot easily be computed using deterministic methods. Therefore, sampling methods became a popular tool in the applied sciences.

Results: Here, we show that sampling methods are not an appropriate tool to analyze qualitative properties of complicated spaces unless RP = NP. We illustrate these results on the example of the thermodynamically feasible flux space of genome-scale metabolic networks and show that with artificial centering hit and run (ACHR) not all reactions that can have variable flux rates are sampled with variables flux rates. In particular a uniform sample of the flux space would not sample the flux variabilities completely.

Conclusion: We conclude that unless theoretical convergence results exist, qualitative results obtained from sampling methods should be considered with caution and if possible double checked using a deterministic method.

Fig 1. Toy network.

Internal reactions r ₁, r ₂, r ₃, r ₄ are irreversible. By thermodynamics, it is not possible to have non-zero flux through r ₁ and also to have a non-zero flux through one of r ₂, r ₃ or r ₄ at the same time.

Fig 2. Flux space of toy network.

The gray area denotes the flux space. In this example it was assumed that input/output flux values are constrained to at most 1. It can be seen that flux v ₁ through r ₁ is exclusive to fluxes v ₂ and v ₃ through r ₂ and r ₃ respectively. Since fluxes through r ₂ can be combined with fluxes through r ₃, the flux space with v ₂, v ₃ > 0 is two-dimensional, while the flux space with v ₁ > 0 is only one-dimensional. Hence, a uniform sample of the flux space would almost surely have zero flux through r ₁.

Fig 3. Sampling results with 10000 sample points.

The y-axis shows the ratio for how many reactions that can have positive/negative flux the sampling method did not sample at least one such flux vector.

Fig 4. Distribution of E. coli iAF1260 flux variability that is missed by sampling.

Histograms (a) and (c) are for the flux space without thermodynamic constraints, histograms (b) and (d) are with thermodynamic constraints. The bins in histograms (a) and (b) count the number of reactions with the respective lower and upper bounds computed by FVA. Bounds equal to 0 are not counted. Histograms (c) and (d) show, for the lower and upper bounds shown in (a) and (b), the number of reactions for which no negative resp. positive flux has been sampled. For all histograms, bin sizes of length 20 were chosen. We remark that zero flux is always possible. Therefore, the flux bounds directly relate to the possible flux range.