TY - GEN A1 - Weber, Marcus A1 - Meyer, Holger T1 - ZIBgridfree - Adaptive Conformation Analysis with qualified Support of Transition States and Thermodynamic Weights N2 - This paper introduces a new algorithm of conformational analysis based on mesh-free methods as described in [M. Weber. Mehless methods in Conformation Dynamics.(2005)]. The adaptive decomposition of the conformational space by softly limiting functions avoids trapping effects and allows adaptive refinement strategies. These properties of the algorithm makes ZIBgridfree particularly suitable for the complete exploration of high-dimensional conformational space. The adaptive control of the algorithm benefits from the tight integration of molecular simulation and conformational analysis. An emphasized part of the analysis is the Robust Perron Cluster Analysis (PCCA+) based on the work of Peter Deuflhard and Marcus Weber. PCCA+ supports an almost-characteristic cluster definition with an outstanding mapping of transition states. The outcome is expressed by the metastable sets of conformations, their thermodynamic weights and flexibility. T3 - ZIB-Report - 05-17 KW - Molecular Dynamics KW - Meshfree Methods KW - Conformation Analysis KW - Quality Functions Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8514 ER - TY - GEN A1 - Fischer, Alexander T1 - An Uncoupling-Coupling Technique for Markov Chain Monte Carlo Methods N2 - Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. By determining almost invariant sets of the associated Markov operator, the Monte Carlo sampling splits by a hierarchical annealing process into the essential regions of the state space; therefore UCMC aims at avoiding the typical metastable behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. The correct weighting factors for the various Markov chains are obtained via a coupling matrix, that connects the samplings from the different almost invariant sets. The underlying mathematical structure of this approach is given by a general examination of the uncoupling-coupling procedure. Furthermore, the overall algorithmic scheme of UCMC is applied to the $n$-pentane molecule, a well-known example from molecular dynamics. T3 - ZIB-Report - 00-04 KW - almost invariant sets KW - bridge sampling KW - cluster analysis KW - hierarchical annealing KW - Markov chains KW - Monte Carlo KW - $n$-pentane molecule KW - ratio of no Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5720 ER - TY - GEN A1 - Haack, Fiete T1 - Properties of Reduced Reversible Markov Chains N2 - The enormous time lag between fast atomic motion and complex pro- tein folding events makes it almost impossible to compute molecular dy- namics on a high resolution. A common way to tackle this problem is to model the system dynamics as a Markov process. Yet for large molec- ular systems the resulting Markov chains can hardly be handled due to the curse of dimensionality. Coarse graining methods can be used to re- duce the dimension of a Markov chain, but it is still unclear how far the coarse grained Markov chain resembles the original system. In order to answer this question, two different coarse-graining methods were analysed and compared: a classical set-based reduction method and an alternative subspace-based approach, which is based on membership vectors instead of sets. On the basis of a small toy system, it could be shown, that in con- trast to the subset-based approach, the subspace-based reduction method preserves the Markov property as well as the essential dynamics of the original system. T3 - ZIB-Report - 08-42 KW - Markov Chain KW - PCCA+ KW - Conformation dynamics Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10941 SN - 1438-0064 ER - TY - GEN A1 - Walter, Lionel A1 - Weber, Marcus T1 - ConfJump : a fast biomolecular sampling method which drills tunnels through high mountains N2 - In order to compute the thermodynamic weights of the different metastable conformations of a molecule, we want to approximate the molecule's Boltzmann distribution in a reasonable time. This is an essential issue in computational drug design. The energy landscape of active biomolecules is generally very rough with a lot of high barriers and low regions. Many of the algorithms that perform such samplings (e.g. the hybrid Monte Carlo method) have difficulties with such landscapes. They are trapped in low-energy regions for a very long time and cannot overcome high barriers. Moving from one low-energy region to another is a very rare event. For these reasons, the distribution of the generated sampling points converges very slowly against the thermodynamically correct distribution of the molecule. The idea of ConfJump is to use $a~priori$ knowledge of the localization of low-energy regions to enhance the sampling with artificial jumps between these low-energy regions. The artificial jumps are combined with the hybrid Monte Carlo method. This allows the computation of some dynamical properties of the molecule. In ConfJump, the detailed balance condition is satisfied and the mathematically correct molecular distribution is sampled. T3 - ZIB-Report - 06-26 KW - Monte Carlo simulation KW - rare events KW - rough potential energy function KW - molecular dynamics Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9204 ER - TY - GEN A1 - Fischer, Alexander A1 - Schütte, Christof A1 - Deuflhard, Peter A1 - Cordes, Frank T1 - Hierarchical Uncoupling-Coupling of Metastable Conformations N2 - Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario. T3 - ZIB-Report - 01-03 KW - almost invariant sets KW - bridge sampling KW - metastability KW - hierarchical annealing KW - hybrid Monte Carlo KW - $n$-pentane molecule KW - ratio of normalizing co Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6296 ER - TY - GEN A1 - Sarich, Marco A1 - Schütte, Christof T1 - Utilizing hitting times for finding metastable sets in non-reversible Markov chains N2 - Techniques for finding metastable or almost invariant sets have been investigated, e.g., for deterministic dynamical systems in set-oriented numerics, for stochastic processes in molecular dynamics, and for random walks on complex networks. Most prominent algorithms are based on spectral apporaches and identify metastable sets via the doimant eigenvalues of the transfer operator associated with the dynamical system under consideration. These algorithms require the dominant eigenvalues to be real-valued. However, for many types of dynamics, e.g. for non-reversible Markov chains, this condition is not met. In this paper we utilize the hitting time apporach to metastable sets and demonstrate how the wellknown statements about optimal metastable decompositions of reversible chains can be reformulated for non-reversible chains if one switches from a spectral approach to an exit time approach. The performance of the resulting algorithm is illustrated by numerical experiments on random walks on complex networks. T3 - ZIB-Report - 14-32 KW - metastability KW - hitting times KW - non-reversible Markov chain KW - directed networks KW - random walk Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51209 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 -