An Uncoupling-Coupling Method for Markov Chain Monte Carlo Simulations with an Application to Biomolecules

Abstract

In this thesis we present the Uncoupling-Coupling Method (UC), a new approach for drawing samples from high-dimensional probability distributions based on the Markov Chain Monte Carlo (MCMC) methodology. MCMC simulations are often hampered by strong metastabilities. This means that the sample path of a Monte Carlo Markov chain jumps rarely if at all within a finite simulation time between metastable sets of the state space, which causes a slow mixing and thus slow convergence of the chain. This problem is addressed in the Uncoupling-coupling method (UC) by hierarchically decomposing the state space into metastable sets and sampling from restricted Monte Carlo Markov chains. UC builds upon MCMC, but also incorporates transfer operator techniques (like exploitation of dominant eigenvectors) and annealing strategies. The uncoupling step allows to draw samples from different parts of the state space by a limited number of rapidly mixing restricted Markov chains. The coupling step guarantees a proper reweighting of all samples to the target distribution. We present the mathematical theory behind UC, and we proof that Monte Carlo Markov chains restricted by UC are indeed rapidly mixing on identified metastable sets. From a MCMC viewpoint UC distinguishes itself from existing auxiliary distributions or parallel sampling techniques by actually decomposing the state space into metastable sets. The UC method is applied and illustrated for n-alkanes and epigallocatechin gallate, a constituent of green tea. In addition to a weighted sample as output of the algorithm, metastable sets identified by UC are closely related to relevant physical conformations of the biomolecule.

Diese Arbeit behandelt die Entkopplungs-Kopplungs-Methode (UC; eng.: Uncoupling-Coupling), ein neuer algorithmischer Ansatz um basierend auf Markov-Ketten-Monte-Carlo (MCMC) eine hochdimensionale Wahrscheinlichkeitsverteilung abzutasten. MCMC-Simulationen werden häufig durch starke Metastabilitäten im Zustandsraum beeinträchtigt. Dies bedeutet, dass der Pfad einer MCMC-Realisierung in endlicher Simulationszeit selten oder gar nicht metastabile Mengen verläßt, was ein langsames Mischen bzw. ungenügende Konvergenz der Markov-Kette nach sich zieht. Diesem Problem wird in UC durch eine hierarchische Unterteilung des Zustandsraums in metastabile Mengen und anschliessender Simulation mittels eingeschränkter Monte-Carlo- Markov-Ketten begegnet. UC baut dabei auf MCMC auf, verbindet dies aber mit Transfer-Operator-Techniken (z.B. Identifikation metastabiler Mengen über dominante Eigenvektoren) und "Annealing"-Strategien. Der Entkopplungsschritt ermöglicht es, mit einer geringen Anzahl schnell mischender eingeschränkter Markov-Ketten verschiedene Bereiche des Zustandsraums abzutasten. Der Kopplungsschritt wiederum garantiert eine korrekte Umgewichtung aller Daten hin zur gewünschten Verteilung. In dieser Arbeit stellen wir die für UC relevanten mathematischen Aspekte dar, und beweisen, dass die auf metastabile Mengen eingeschränkten Markov-Ketten schnell mischend sind. Aus Sicht der MCMC-Methodik unterscheidet sich UC von alternativen algorithmischen Ansätzen durch eine konsequente Unterteilung des Zustandsraums in metastabile Mengen. Die UC-Methode wird auf n-Alkane und Epigallocatechin Gallate (ein im grünen Tee vorkommendes Biomolekül) angewandt. Bei derartigen biomolekularen Anwendungen kommt neben einer korrekten Abtastung des Zustandsraums hinzu, dass die durch UC identifizierten metastabilen Mengen sehr stark physikalische Konformationen des jeweiligen Biomoleküls widerspiegeln.