572
eng
reportzib
0
2000-03-01
2000-03-01
--
An Uncoupling-Coupling Technique for Markov Chain Monte Carlo Methods
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.
00-04
573
urn:nbn:de:0297-zib-5720
Alexander Fischer
ZIB-Report
00-04
eng
uncontrolled
almost invariant sets
eng
uncontrolled
bridge sampling
eng
uncontrolled
cluster analysis
eng
uncontrolled
hierarchical annealing
eng
uncontrolled
Markov chains
eng
uncontrolled
Monte Carlo
eng
uncontrolled
$n$-pentane molecule
eng
uncontrolled
ratio of no
Informatik, Informationswissenschaft, allgemeine Werke
Computational methods in Markov chains [See also 65C40]
Monte Carlo methods
Computational Markov chains
Numerical methods (Monte Carlo, series resummation, etc.) [See also 65-XX, 81T80]
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/572/ZR-00-04.ps
https://opus4.kobv.de/opus4-zib/files/572/ZR-00-04.pdf
687
eng
reportzib
0
2002-04-11
2002-04-11
--
From Molecular Dynamics to Conformational Dynamics in Drug Design
Computational drug design studies molecular recognition in the {\em virtual lab}. The arising Hamiltonian dynamics is known to be chaotic and ill-conditioned already after picoseconds, whereas times are $msec$ up to $min$. Classical molecular dynamics with long term trajectory computation gives, at best, information about time and statistical ensemble averages. The present paper surveys a recent new modeling approach called {\em conformational dynamics}, which is due to the author and Ch. Schütte. This approach achieves information about the dy time scales by telescoping a short term deterministic model with a statistical model. Examples of small biomolecules are included.
02-20
688
urn:nbn:de:0297-zib-6878
Appeared in: M. Kirkilionis, S. Krömker, R. Rannacher, F. Toni (eds.) Trends in Nonlinear Analysis. Springer 2003, pp. 269-288
Peter Deuflhard
ZIB-Report
02-20
eng
uncontrolled
molecular dynamics
eng
uncontrolled
conformational dynamics
eng
uncontrolled
drug design
eng
uncontrolled
Hamiltonian dynamics
eng
uncontrolled
almost invariant sets
eng
uncontrolled
transition operator
eng
uncontrolled
Markov chain
eng
uncontrolled
Perro
Informatik, Informationswissenschaft, allgemeine Werke
Applications to biology and medical sciences
Monte Carlo methods
Eigenvalues, eigenvectors
Initial value problems
Improperly posed problems
Numerical Mathematics
Computational Medicine
Deuflhard, Peter
https://opus4.kobv.de/opus4-zib/files/687/ZR-02-20.ps
https://opus4.kobv.de/opus4-zib/files/687/ZR-02-20.pdf
742
eng
reportzib
0
2003-07-02
2003-07-02
--
Molecular Conformation Dynamics and Computational Drug Design
The paper surveys recent progress in the mathematical modelling and simulation of essential molecular dynamics. Particular emphasis is put on computational drug design wherein time scales of $msec$ up to $min$ play the dominant role. Classical long-term molecular dynamics computations, however, would run into ill-conditioned initial value problems already after time spans of only $psec=10^{-12} sec$. Therefore, in order to obtain results for times of pharmaceutical interest, a combined deterministic-stochastic model is needed. The concept advocated in this paper is the direct identification of metastable conformations together with their life times and their transition patterns. It can be interpreted as a {\em transfer operator} approach corresponding to some underlying hybrid Monte Carlo process, wherein short-term trajectories enter. Once this operator has been discretized, which is a hard problem of its own, a stochastic matrix arises. This matrix is then treated by {\em Perron cluster analysis}, a recently developed cluster analysis method involving the numerical solution of an eigenproblem for a Perron cluster of eigenvalues. In order to avoid the 'curse of dimension', the construction of appropriate boxes for the spatial discretization of the Markov operator requires careful consideration. As a biomolecular example we present a rather recent SARS protease inhibitor.
03-20
743
urn:nbn:de:0297-zib-7427
Appeared in: J. M. Hill, R. Moore (eds.) Applied Mathematics Entering the 21st Century. Proc. ICIAM 2003, Sydney, Australia, 2004, pp. 91-119 (2004)
Peter Deuflhard
Christof Schütte
ZIB-Report
03-20
eng
uncontrolled
conformation dynamics
eng
uncontrolled
Monte Carlo methods
eng
uncontrolled
transfer operations
eng
uncontrolled
Hamiltonian dynamics
eng
uncontrolled
Smoluchowski dynamics
eng
uncontrolled
metastable sets
eng
uncontrolled
Perron cluster an
Informatik, Informationswissenschaft, allgemeine Werke
Monte Carlo methods
Computational Markov chains
Hamiltonian systems including symplectic integrators
ZIB Allgemein
Deuflhard, Peter
Schütte, Christof
https://opus4.kobv.de/opus4-zib/files/742/ZR-03-20.ps
https://opus4.kobv.de/opus4-zib/files/742/ZR-03-20.pdf
1131
eng
doctoralthesis
0
2009-06-03
2009-06-03
2008-12-17
Statistical Error Estimation and Grid-free Hierarchical Refinement in Conformation Dynamics
The understanding of geometric structures and dynamical properties of molecular conformations gives insight into molecular long-term behavior. The identification of metastable conformations together with their life times and transition patterns is the intention of conformation dynamics. Conformation dynamics is a multi-scale approach that leads to a reduced description of the dynamical system in terms of a stochastic transition probability matrix. The present thesis deals with the error analysis of computed matrices and the resulting matrix functions. Since conformational membership vectors, as they are computed by the Robust Perron Cluster Analysis (PCCA+), form an invariant subspace of the transition matrix, subspace-based error estimators are of particular interest. The decomposition of the state space into basis functions and the approximation of integrals by Monte-Carlo quadrature give rise to row-wise correlated random matrices, for which stochastic norms are computed. Together with an appropriate statistical model for the distribution of matrix rows, this allows for the calculation of error bounds and error distributions of the invariant subspace and other variables of interest. Equilibration of errors among the basis functions can be achieved by enhanced sampling in regions where the trajectories are mixing slowly. Hierarchical refinement of such basis functions systematically improves the clustering into metastable conformations by reducing the error in the corresponding invariant subspace. These techniques allow for an evaluation of simulation results and pave the way for the analysis of larger molecules. Moreover, the extension of PCCA+ to non-reversible Markov chains, verified by the corresponding perturbation theory, and the modification of the objective function for the case of soft membership vectors represent a further generalization of the clustering method, thus continuing the development from PCCA over PCCA+ to PCCA++. The methods developed in this thesis are useful for but not limited to conformation dynamics. In fact, they are applicable to a broader class of problems which combine domain decomposition with Monte-Carlo quadrature. Possible application areas may include the chemical master equation or quantum dynamical systems.
Das Verständnis von geometrischen Strukturen und dynamischen Eigenschaften molekularer Konformationen ist essentiell für die Vorhersage des Langzeitverhaltens von Molekülen. Die Identifikation metastabiler Konformationen sowie die Bestimmung von Übergangswahrscheinlichkeiten und Haltezeiten sind Bestandteil der Konformationdynamik. Dabei handelt es sich um eine Mehrskalenmethode, die auf eine reduzierte Beschreibung des Systems mittels einer stochastischen Übergangsmatrix führt. In der vorliegenden Dissertation wurde untersucht, wie man die Genauigkeit der Matrizen sowie der daraus berechneten Größen quantifizieren kann. Im Mittelpunkt stehen dabei Fehlerschätzer für den invarianten Unterraum, da die rechten Eigenvektoren als Grundlage der Robusten Perron Cluster Analyse (PCCA+) zur Identifizierung der metastabilen Konformationen dienen. Die Zerlegung des Zustandsraumes in Basisfunktionen sowie die Approximation der Matrixeinträge mittels Monte-Carlo-Quadratur führen zu zeilenweise korrelierten Zufallsmatrizen. Mit Hilfe einer stochastischen Norm sowie einem geeigneten statistischen Modell für die Verteilung der Matrixzeilen können u.a. Fehlerschranken und -verteilungen für den invarianten Unterraum brechnet werden. Eine Equilibrierung des Fehlers zwischen den Basisfunktionen kann durch erweitertes Sampling in solchen Regionen erreicht werden, in denen die Trajektorien nur langsam mischen.Eine hierarchische Zerlegung dieser Basisfunktionen verbessert systematisch die Zerlegung in metastabile Konformationen, indem sie den Fehler im invarianten Unterraum reduziert. Diese Techniken gestatten eine Evaluierung der Simulationsergebnisse und ebnen den Weg zur Behandlung komplexerer Moleküle. Desweiteren wurden Verallgemeinerungen der PCCA+ untersucht. Die Erweiterung der PCCA+ auf nicht-reversible Markov-Ketten sowie die Modifizierung der Zielfunktion für den Fall der weichen Clusterung setzen die Entwicklung von der PCCA über PCCA+ zu PCCA++ fort. Somit können neue Anwendungsfelder für dieses Cluster-Verfahren erschlossen werden. Die Methoden wurden zwar in Rahmen der Konformationsdynamik entwickelt, jedoch lassen sie sich auf eine weite Problemklasse anwenden, in der Gebietszerlegungsverfahren mit Monte-Carlo-Quadratur kombiniert werden. Mögliche Anwendungsgebiete umfassen die chemische Master-Gleichung oder quantenchemische Systeme.
1180
urn:nbn:de:kobv:188-fudissthesis000000008079-9
Susanna Röblitz
unknown unknown
Peter Deuflhard
Wilhelm Huisinga
deu
uncontrolled
Konformationsdynamik
deu
uncontrolled
Metastabilität
deu
uncontrolled
gitterfreie Methoden
deu
uncontrolled
Monte-Carlo-Quadratur
deu
uncontrolled
Perron-Cluster-Analyse
eng
uncontrolled
conformation dynamics
eng
uncontrolled
metastability
eng
uncontrolled
mesh-free methods
eng
uncontrolled
Monte Carlo quadrature
eng
uncontrolled
Perron cluster analysis
Mathematik
Simulation
Computational methods for ergodic theory (approximation of invariant measures, computation of Lyapunov exponents, entropy)
Markov processes: estimation
Monte Carlo methods
Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
Dissertationen
Numerical Mathematics
Röblitz, Susanna
Matheon-A19
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/1131/thesis_final_el.pdf
388
eng
reportzib
0
1999-01-04
1999-01-04
--
A Direct Approach to Conformational Dynamics based on Hybrid Monte Carlo
Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator $T$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of $T$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix $P$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of $T$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted.
SC-98-45
389
urn:nbn:de:0297-zib-3889
Appeared in: Journal of Computational Physics 151, 146-168 (1999)
Christof Schütte
Alexander Fischer
Wilhelm Huisinga
Peter Deuflhard
ZIB-Report
SC-98-45
eng
uncontrolled
conformation
eng
uncontrolled
conformational dynamics
eng
uncontrolled
hybrid Monte Carlo
eng
uncontrolled
reweighting
eng
uncontrolled
essential degrees of freedom
eng
uncontrolled
transition probabilities
eng
uncontrolled
Markov operator
Informatik, Informationswissenschaft, allgemeine Werke
Eigenvalue problems [See also 47J10, 49R05]
Operators on function spaces (general)
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) [See also 90B30, 91D10, 91D35, 91E40]
Monte Carlo methods
ZIB Allgemein
Deuflhard, Peter
Schütte, Christof
https://opus4.kobv.de/opus4-zib/files/388/SC-98-45.ps
https://opus4.kobv.de/opus4-zib/files/388/SC-98-45.pdf
920
eng
reportzib
0
2006-05-09
2006-05-09
--
ConfJump : a fast biomolecular sampling method which drills tunnels through high mountains
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.
06-26
920
urn:nbn:de:0297-zib-9204
Lionel Walter
Marcus Weber
ZIB-Report
06-26
eng
uncontrolled
Monte Carlo simulation
eng
uncontrolled
rare events
eng
uncontrolled
rough potential energy function
eng
uncontrolled
molecular dynamics
Informatik, Informationswissenschaft, allgemeine Werke
Dynamical systems in statistical mechanics [See also 82Cxx]
Computational methods in Markov chains [See also 65C40]
Monte Carlo methods
Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/920/ZR-06-26.pdf
https://opus4.kobv.de/opus4-zib/files/920/ZR-06-26.ps
422
eng
reportzib
0
1999-09-21
1999-09-21
--
Differential Equations in Technology and Medicine. Computational Concepts, Adaptive Algorithms, and Virtual
Labs
This series of lectures has been given to a class of mathematics postdocs at a European summer school on Computational Mathematics Driven by Industrial Applications in Martina Franca, Italy (organized by CIME). It deals with a variety of challenging real life problems selected from clinical cancer therapy, communication technology, polymer production, and pharmaceutical drug design. All of these problems from rather diverse application areas share two common features: (a) they have been modelled by various differential equations -- elliptic, parabolic, or Schrödinger--type partial differential equations, countable ordinary diffential equations, or Hamiltonian systems, (b) their numerical solution has turned out to be real challenge to computational mathematics.
SC-99-34
423
urn:nbn:de:0297-zib-4223
Appeared in: Computational Mathematics Driven by Industrial Problems. Springer 2000. Lecture Notes in Mathematics, 1739, pp. 69-125
Peter Deuflhard
ZIB-Report
SC-99-34
eng
uncontrolled
differential equations:
eng
uncontrolled
ordinary
eng
uncontrolled
partial
eng
uncontrolled
countable
eng
uncontrolled
hamiltonian
eng
uncontrolled
finite element methods:
eng
uncontrolled
adaptive
eng
uncontrolled
multilevel
eng
uncontrolled
grid generation
eng
uncontrolled
medical t
Informatik, Informationswissenschaft, allgemeine Werke
Research exposition (monographs, survey articles)
Monte Carlo methods
Models, numerical methods [See also 68U20]
Eigenvalues, eigenvectors
Equations with linear operators (do not use 65Fxx)
Initial value problems
Improperly posed problems
Eigenvalue problems
Finite elements, Rayleigh-Ritz and Galerkin methods, finite methods
Multigrid methods; domain decomposition
Antennas, wave-guides
ZIB Allgemein
Deuflhard, Peter
https://opus4.kobv.de/opus4-zib/files/422/SC-99-34.ps
https://opus4.kobv.de/opus4-zib/files/422/SC-99-34.pdf
406
eng
habilitation
0
1999-06-14
1999-06-14
--
Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules
The function of many important biomolecules comes from their dynamic properties and their ability to switch between different {\em conformations}. In a conformation, the large scale geometric structure of the molecule is understood to be conserved, whereas on smaller scales the system may well rotate, oscillate or fluctuate. In a recent article [J. Comp. Phys., 151,1 (1999)], the present author and coworkers demonstrated that (a) conformations can be understood as almost invariant sets of some Markov chain being defined via the Hamiltonian system governing the molecular dynamics and that (b) these sets can efficiently be computed via eigenvectors of the corresponding Markov operator. The persent manuscript reviews the mathematical modelling steps behind the novel concept, includes a rigorous analytical justification of this approach and especially of the numerical details of the algorithm, and illustrates its performance when applied to realistic molecular systems.
SC-99-18
407
urn:nbn:de:0297-zib-4063
Christof Schütte
ZIB-Report
SC-99-18
eng
uncontrolled
biochemical conformation
eng
uncontrolled
almost invariant set
eng
uncontrolled
Markov chain
eng
uncontrolled
Hamiltonian system
eng
uncontrolled
Markov operator
eng
uncontrolled
quasi-compact operator
eng
uncontrolled
Perron root
eng
uncontrolled
Perron-
Informatik, Informationswissenschaft, allgemeine Werke
Perturbations, asymptotics
Probabilistic methods in Banach space theory [See also 60Bxx]
Continuous-time Markov processes on discrete state spaces
Monte Carlo methods
Classical dynamic and nonequilibrium statistical mechanics (general)
ZIB Allgemein
Habilitationen
Schütte, Christof
https://opus4.kobv.de/opus4-zib/files/406/SC-99-18.ps
https://opus4.kobv.de/opus4-zib/files/406/SC-99-18.pdf
629
eng
reportzib
0
2001-02-23
2001-02-23
--
Hierarchical Uncoupling-Coupling of Metastable Conformations
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.
01-03
630
urn:nbn:de:0297-zib-6296
Appeared in: Computational Methods for Macromolecules: Challenges and Applications. Proc. of the 3rd Int. Workshop on Methods for Macromolecular Modeling, New York, Oct. 12-14, 2000. T. Schlick, Gan, H. H. (eds.) Springer 2002. LNCSE 24, pp. 235-259
Alexander Fischer
Christof Schütte
Peter Deuflhard
Frank Cordes
ZIB-Report
01-03
eng
uncontrolled
almost invariant sets
eng
uncontrolled
bridge sampling
eng
uncontrolled
metastability
eng
uncontrolled
hierarchical annealing
eng
uncontrolled
hybrid Monte Carlo
eng
uncontrolled
$n$-pentane molecule
eng
uncontrolled
ratio of normalizing co
Informatik, Informationswissenschaft, allgemeine Werke
Computational methods in Markov chains [See also 65C40]
Monte Carlo methods
Computational Markov chains
Numerical methods (Monte Carlo, series resummation, etc.) [See also 65-XX, 81T80]
ZIB Allgemein
Deuflhard, Peter
Schütte, Christof
https://opus4.kobv.de/opus4-zib/files/629/ZR-01-03.ps
https://opus4.kobv.de/opus4-zib/files/629/ZR-01-03.pdf
4972
eng
reportzib
0
--
2014-04-23
--
Applications of the cross-entropy method to importance sampling and optimal control of diffusions
We study the cross-entropy method for diffusions. One of the results is a versatile cross-entropy algorithm that can be used to design efficient importance sampling strategies for rare events or to solve optimal control problems. The approach is based on the minimization of a suitable cross-entropy functional, with a parametric family of exponentially tilted probability distributions. We illustrate the new algorithm with several numerical examples and discuss algorithmic issues and possible extensions of the method.
1438-0064
urn:nbn:de:0297-zib-49720
10.1137/14096493X
yes
Appeared in: Siam Journal on Scientific Computing 36 (2014) A 2654-A2672
Wei Zhang
Erlinda Körnig
Han Wang
Carsten Hartmann
Marcus Weber
Christof Schütte
ZIB-Report
14-10
eng
uncontrolled
important sampling
eng
uncontrolled
optimal control
eng
uncontrolled
cross-entropy method
eng
uncontrolled
rare events
eng
uncontrolled
change of measure
Monte Carlo methods
Optimal stochastic control
Measures of information, entropy
Numerical Mathematics
Schütte, Christof
Weber, Marcus
NonequiMSM
SFB1114-A5
https://opus4.kobv.de/opus4-zib/files/4972/ZIB-Report_14-10.pdf