TY - GEN A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes N2 - 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. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - GEN A1 - Weber, Marcus A1 - Fackeldey, Konstantin T1 - G-PCCA: Spectral Clustering for Non-reversible Markov Chains N2 - Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g., the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We extend this spectral clustering method also to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension, non-reversible Markov chains can be analyzed. Furthermore, the chains need not have a positive stationary distribution. And additionally to metastabilities, dominant cycles and sinks can be identified, too. T3 - ZIB-Report - 15-35 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55505 ER - TY - GEN A1 - Bujotzek, Alexander A1 - Schütt, Ole A1 - Nielsen, Adam A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - Efficient Conformational Analysis by Partition-of-Unity Coupling T2 - Math Chem N2 - Obtaining a sufficient sampling of conformational space is a common problem in molecular simulation. We present the implementation of an umbrella-like adaptive sampling approach based on function-based meshless discretization of conformational space that is compatible with state of the art molecular dynamics code and that integrates an eigenvector-based clustering approach for conformational analysis and the computation of inter-conformational transition rates. The approach is applied to three example systems, namely n-pentane, alanine dipeptide, and a small synthetic host-guest system, the latter two including explicitly modeled solvent. T3 - ZIB-Report - 13-58 KW - Markov State Models KW - Meshfree KW - Molecular Simulation KW - Partition of Unity Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42570 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin A1 - Sikorski, Alexander A1 - Weber, Marcus T1 - Spectral Clustering for Non-reversible Markov Chains N2 - Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g. the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We also extend this spectral clustering method to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension non-reversible Markov chains can be analyzed. Furthermore, the chains do not need to have a positive stationary distribution. In addition to metastabilities, dominant cycles and sinks can also be identified. This novel method is called GenPCCA (i.e. Generalized PCCA), since it includes the case of non reversible processes. We also apply the method to real world eye tracking data. T3 - ZIB-Report - 18-48 KW - spectral clustering KW - Markov chain KW - Schur decomposition KW - non-reversible Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70218 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin T1 - Coupling Meshbased and Meshfree Methods by a Transfer Operator Approach N2 - In contrast to the well known meshbased methods like the finite element method, meshfree methods do not rely on a mesh. However besides their great applicability, meshfree methods are rather time consuming. Thus, it seems favorable to combine both methods, by using meshfree methods only in a small part of the domain, where a mesh is disadvantageous, and a meshbased method for the rest of the domain. We motivate, that this coupling between the two simulation techniques can be considered as saddle point problem and show the stability of this coupling. Thereby a novel transfer operator is introduced, which interacts in the transition zone, where both methods coexist. T3 - ZIB-Report - 10-12 KW - Gitterlose Methoden KW - inf-sup-Bedingung KW - Kopplung KW - meshfree KW - meshbased KW - inf-sup-Condition Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11755 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin A1 - Röblitz, Susanna A1 - Scharkoi, Olga A1 - Weber, Marcus T1 - Soft Versus Hard Metastable Conformations in Molecular Simulations N2 - Particle methods have become indispensible in conformation dynamics to compute transition rates in protein folding, binding processes and molecular design, to mention a few. Conformation dynamics requires at a decomposition of a molecule's position space into metastable conformations. In this paper, we show how this decomposition can be obtained via the design of either ``soft'' or ``hard'' molecular conformations. We show, that the soft approach results in a larger metastabilitiy of the decomposition and is thus more advantegous. This is illustrated by a simulation of Alanine Dipeptide. T3 - ZIB-Report - 11-27 KW - Proteins, Conformation Space, Meshfree Methods Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13189 ER - TY - GEN A1 - Weber, Marcus A1 - Fackeldey, Konstantin T1 - Computing the Minimal Rebinding Effect Included in a Given Kinetics N2 - The rebinding effect is a phenomenon which occurs when observing a ligand-receptor binding process. On the macro scale this process comprises the Markov property. This Makovian view is spoiled when switching to the atomistic scale of a binding process. We therefore suggest a model which accurately describes the rebinding effect on the atomistic scale by allowing ''intermediate'' bound states. This allows us to define an indicator for the magnitude of rebinding and to formulate an optimization problem. The results form our examples show good agreement with data form laboratory. T3 - ZIB-Report - 13-12 KW - Rebinding KW - Molecular Kinetics KW - Conformation Dynamics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17796 SN - 1438-0064 ER - TY - GEN A1 - Nielsen, Adam A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - On a Generalized Transfer Operator N2 - We introduce a generalized operator for arbitrary stochastic processes by using a pre-kernel, which is a generalization of the Markov kernel. For deterministic processes, such an operator is already known as the Frobenius-Perron operator, which is defined for a large class of measures. For Markov processes, there exists transfer operators being only well defined for stationary measures in $L^2$. Our novel generalized transfer operator is well defined for arbitrary stochastic processes, in particular also for deterministic ones. We can show that this operator is acting on $L^1$. For stationary measures, this operator is also an endomorphism of $L^2$ and, therefore, allows for a mathematical analysis in Hilbert spaces. T3 - ZIB-Report - 13-74 KW - Transfer Operator KW - Pre Kernel KW - Perron Frobenius Generalization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43162 SN - 1438-0064 ER - TY - GEN A1 - Krause, Dorian A1 - Fackeldey, Konstantin A1 - Krause, Rolf T1 - A parallel multiscale simulation toolbox for coupling molecular dynamics and finite elements N2 - It is the ultimate goal of concurrent multiscale methods to provide computational tools that allow to simulation physical processes with the accuracy of micro-scale and the computational speed of macro-scale models. As a matter of fact, the efficient and scalable implementation of concurrent multiscale methods on clusters and supercomputers is a complicated endeavor. In this article we present the parallel multiscale simulation tool MACI which has been designed for efficient coupling between molecular dynamics and finite element codes. We propose a specification for a thin yet versatile interface for the coupling of molecular dynamics and finite element codes in a modular fashion. Further we discuss the parallelization strategy pursued in MACI, in particular, focusing on the parallel assembly of transfer operators and their efficient execution. T3 - ZIB-Report - 13-50 KW - Parallel KW - Atomistic to Continuum KW - Multiscale KW - MACI KW - Meshfree Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42354 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - A square root approximation of transition rates for a Markov State Model N2 - Trajectory- or mesh-based methods for analyzing the dynamical behavior of large molecules tend to be impractical due to the curse of dimensionality - their computational cost increases exponentially with the size of the molecule. We propose a method to break the curse by a novel square root approximation of transition rates, Monte Carlo quadrature and a discretization approach based on solving linear programs. With randomly sampled points on the molecular energy landscape and randomly generated discretizations of the molecular configuration space as our initial data, we construct a matrix describing the transition rates between adjacent discretization regions. This transition rate matrix yields a Markov State Model of the molecular dynamics. We use Perron cluster analysis and coarse-graining techniques in order to identify metastable sets in configuration space and approximate the transition rates between the metastable sets. Application of our method to a simple energy landscape on a two-dimensional configuration space provides proof of concept and an example for which we compare the performance of different discretizations. We show that the computational cost of our method grows only polynomially with the size of the molecule. However, finding discretizations of higher-dimensional configuration spaces in which metastable sets can be identified remains a challenge. T3 - ZIB-Report - 13-43 KW - Markov State Models KW - Markov chains KW - meshfree methods KW - metastability KW - Voronoi KW - linear programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42195 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin A1 - Koltai, Péter A1 - Névir, Peter A1 - Rust, Henning A1 - Schild, Axel A1 - Weber, Marcus T1 - From Metastable to Coherent Sets - time-discretization schemes N2 - Given a time-dependent stochastic process with trajectories x(t) in a space $\Omega$, there may be sets such that the corresponding trajectories only very rarely cross the boundaries of these sets. We can analyze such a process in terms of metastability or coherence. Metastable sets M are defined in space $M\subset\Omega$, coherent sets $M(t)\subset\Omega$ are defined in space and time. Hence, if we extend the space by the time-variable t, coherent sets are metastable sets in $\Omega\times[0,\infty]$. This relation can be exploited, because there already exist spectral algorithms for the identification of metastable sets. In this article we show that these well-established spectral algorithms (like PCCA+) also identify coherent sets of non-autonomous dynamical systems. For the identification of coherent sets, one has to compute a discretization (a matrix T) of the transfer operator of the process using a space-timediscretization scheme. The article gives an overview about different time-discretization schemes and shows their applicability in two different fields of application. T3 - ZIB-Report - 17-74 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66074 SN - 1438-0064 ER - TY - GEN A1 - Weber, Marcus A1 - Fackeldey, Konstantin A1 - Schütte, Christof T1 - Set-free Markov State Building N2 - Molecular dynamics (MD) simulations face challenging problems since the timescales of interest often are much longer than what is possible to simulate and even if sufficiently long simulation are possible the complex nature of the resulting simulation data makes interpretation difficult. Markov State Models (MSMs) help to overcome these problems by making experimentally relevant timescales accessible via coarse grained representations that also allows for convenient interpretation. However, standard set-based MSMs exhibit some caveats limiting their approximation quality and statistical significance. One of the main caveats results from the fact that typical MD trajectories repeatedly re-cross the boundary between the sets used to build the MSM which causes statistical bias in estimating the transition probabilities between these sets. In this article, we present a set-free approach to MSM building utilizing smooth overlapping ansatz functions instead of sets and an adaptive refinement approach. This kind of meshless discretization helps to overcome the recrossing problem and yields an adaptive refinement procedure that allows to improve the quality of the model while exploring state space and inserting new ansatz functions into the MSM. T3 - ZIB-Report - 17-10 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62167 SN - 1438-0064 ER -