Optimization Online


Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes

Isabel Beckenbach(beckenbach***at***zib.de)
Leon Eifler(eifler***at***zib.de)
Konstantin Fackeldey(fackeldey***at***zib.de)
Ambros Gleixner(gleixner***at***zib.de)
Andreas Grever(grever***at***zib.de)
Marcus Weber(weber***at***zib.de)
Jakob Witzig(witzig***at***zib.de)

Abstract: In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.

Keywords: Markov State Models; Mixed-Integer Programming; NESS; Non-reversible Markov Processes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- Science and Engineering (Chemical Engineering )

Category 3: Other Topics (Optimization of Simulated Systems )

Citation: ZIB-Report 16-39, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany, 08/2016

Download: [PDF]

Entry Submitted: 09/06/2016
Entry Accepted: 09/06/2016
Entry Last Modified: 09/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society