Mixed-integer programming for cycle detection in nonreversible Markov processes

DOI10.1137/16M1091162zbMATH Open1391.60170arXiv1609.02063OpenAlexW2963343287MaRDI QIDQ4643799FDOQ4643799

Authors: Jakob Witzig, Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros M. Gleixner, Andreas Grever, Marcus Weber 

Publication date: 29 May 2018

Published in: Multiscale Modeling & Simulation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1609.02063

Recommendations

• Finding dominant structures of nonreversible Markov processes
• Nonstationary cyclic behavior in Markov systems
• scientific article; zbMATH DE number 3864241
• scientific article; zbMATH DE number 7365760
• Reversible Markov Decision Processes with an Average-Reward Criterion

zbMATH Keywords

mixed-integer programmingMarkov state modelsnonreversible Markov processesNESS

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Combinatorial optimization (90C27) Discrete-time Markov processes on general state spaces (60J05) Mixed integer programming (90C11) Statistical thermodynamics (82B30)

Cites Work

• Handbook of Markov Chain Monte Carlo
• An Efficient Heuristic Procedure for Partitioning Graphs
• Robust Perron cluster analysis in conformation dynamics
• An Automatic Method of Solving Discrete Programming Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Approximation of Complicated Dynamical Behavior
• The Complexity of Multiterminal Cuts
• Low-discrepancy and low-dispersion sequences
• On the solution of traveling salesman problems
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• A tree-search algorithm for mixed integer programming problems
• An introduction to Markov state models and their application to long timescale molecular simulation
• L’algebre de Boole et ses applications en recherche operationnelle
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains
• Modularity of directed networks: cycle decomposition approach
• On the knapsack closure of 0-1 integer linear programs
• Computing the nearest reversible Markov chain.
• Finding dominant structures of nonreversible Markov processes
• Computing the Minimal Rebinding Effect Included in a Given Kinetics

Cited In (1)

• Conflict Analysis for MINLP

Uses Software

• SCIP

This page was built for publication: Mixed-integer programming for cycle detection in nonreversible Markov processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4643799)