Search

1 Introduction 1 2 Markov Processes 7 2.1 Markov Jump Processes . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 The Generator Matrix . . . . . . . . . . . . . . . . . . 8 2.1.2 The Imbedding Problem . . . . . . . . . . . . . . . . . 9 2.1.3 Necessary Conditions for the Existence of a Generator 11 2.1.4 Uniqueness of the Generator . . . . . . . . . . . . . . 14 2.1.5 Imbedding of Perturbed Generator Matrices . . . . . . 15 2.2 The Ornstein-Uhlenbeck Process . . . . . . . . . . . . . . . . 17 3 Hidden Markov Models 22 3.1 The EM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 The Baum- Welch Algorithm . . . . . . . . . . . . . . . 27 3.1.2 Metastability Analysis with HMMs . . . . . . . . . . . 29 4 Parameter Estimation for Ornstein- Uhlenbeck Processes 31 4.1 Propagation of the Probability Density . . . . . . . . . . . . . 31 4.1.1 Further Simplification . . . . . . . . . . . . . . . . . . 34 4.2 Optimal Parameters via the Maximum Likelihood Principle . 34 4.3 Multi-Dimensional Parameter Estimation without Euler Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5 HMMSDE 40 5.1 Model Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2.1 Likelihood Function . . . . . . . . . . . . . . . . . . . 42 5.3 Partial Observability . . . . . . . . . . . . . . . . . . . . . . . 43 5.3.1 Expectation Step . . . . . . . . . . . . . . . . . . . . . 43 5.3.2 Maximization Step . . . . . . . . . . . . . . . . . . . . 44 5.4 Enhancements and Application . . . . . . . . . . . . . . . . . 44 5.5 Illustrative Example: Three-Hole Potential . . . . . . . . . . 46 6 Parameter Estimation for Markov Jump Processes 53 6.1 Discrete Likelihood . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Continuous Likelihood . . . . . . . . . . . . . . . . . . . . . . 54 6.3 Finding an Optimal Generator under Partial (Discrete) Observation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.3.1 The Expectation Step . . . . . . . . . . . . . . . . . . 59 6.3.2 The Maximization Step . . . . . . . . . . . . . . . . . 63 6.4 Comparison and Discussion of the Maximum Likelihood Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.4.1 Resolvent Method . . . . . . . . . . . . . . . . . . . . 64 i 6.4.2 Quadratic Optimization Method . . . . . . . . . . . . 65 6.4.3 Pros and Cons . . . . . . . . . . . . . . . . . . . . . . 66 6.4.4 Perturbation Theory . . . . . . . . . . . . . . . . . . . 68 6.5 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . 69 6.5.1 Generator Estimation under Perturbation . . . . . . . 69 6.5.2 A Metastable Generator . . . . . . . . . . . . . . . . . 71 7 HMM with Generator Estimation 74 7.1 Hidden Markov Jump Process . . . . . . . . . . . . . . . . . . 74 7.1.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.1.2 Parameter Estimation . . . . . . . . . . . . . . . . . . 78 7.1.3 Numerical Examples . . . . . . . . . . . . . . . . . . . 80 7.2 Markov Jump Output Process . . . . . . . . . . . . . . . . . . 89 7.2.1 Model Design . . . . . . . . . . . . . . . . . . . . . . . 90 7.2.2 Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2.3 Partial Observability . . . . . . . . . . . . . . . . . . . 91 7.2.4 Example: Recovering an HMM-MJP from a Realization with Varying Time Lag . . . . . . . . . . . . . . . 92 7.2.5 Example: A Metastable Generator Revisited . . . . . 99 7.2.6 Example: A Discrete Generator for an Smoluchowski Process . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.3 Alternative Approaches to HMM Variants . . . . . . . . . . . 109 8 Summary 111 9 Zusammenfassung 112, In this thesis a set of procedures for the analysis of time series was developed. The models introduced here are based on the concept of Hidden Markov models. A hidden Markov model (HMM) consists of two stochastic processes. However, only one of these is observable. The HMM variants presented herein have been developed with regard to a prospective application to biomolecular time series. Therefore, the investigated time series are realizations of processes that can be characterized as follows: They jump between metastable states. The correlation times are small with respect to the exit times from a metastable state. On a time scale, chosen in such a way that the process is Markovian, these jumps occur instantaneously. That is: Transitions between metastable states in equilibrium take place in one or very few time steps. By means of the presented methods in particular, the question how metastable states can be distinguished by kinetic patterns is addressed. The local dynamics are modeled either by a space-discrete Markov jump process or by a continuous diffusion process. Both concepts are discussed by means of several examples. Particularly we focussed on the issue of generator estimation. The combination of the generator estimation with the concept of the hidden Markov model is new. It allows for analyzing time-continuous processes with standard HMM techniques. Especially the time-continuity of the model makes the analysis of time series with varying time lags possible. Furthermore, a model with Markov jump output process has the advantage that the process is determined by the generator matrix only. Hence no additional assumption about the distribution of the data is required. Beyond this in the examples we observed that even if the box-discretization is rather coarse- grained, the local dynamics still can be expressed satisfactorily by an HMM- MJP. In the scope of this thesis HMM-MJP was applied to small systems, generated by Smoluchowski dynamics, by a discrete generator or by an HMM itself. However, the algorithms are applicable to the high-dimensional case. How HMM-MJP performs in the application to larger systems - such as the simulation of biomolecules - has to be clarified in further investigations. Difficulties arising with larger systems are on the one hand computational costs and on the other hand cumulations of small entries in the generator matrix. Too many small entries close to zero can lead to numerical instabilities. One approach to handle these problems is the restriction of the state space as described in the examples 7.2.5 and 7.2.6., In dieser Arbeit wurde ein Verfahrenskatalog zur Zeitreihenanalyse metastabiler Systeme entwickelt. Die hier eingeführten Modelle basieren auf dem Konzept der Hidden Markov Modelle. Ein Hidden Markov Modell (HMM) besteht aus zwei stochastischen Prozessen, von denen nur einer beobachtbar ist. Die HMM-Varianten in dieser Arbeit wurden im Hinblick auf die spätere Anwendung auf Biomolekuelzeitreihen entwickelt. Deshalb sind die zu analysierenden Zeitreihen Realisierungen von Prozessen, die sich wie folgt charakterisieren lassen: Sie springen zwischen metastabilen Zustaenden. Die Korrelationsszeiten sind im Vergleich zu den Austrittszeiten aus einem metastabilen Zustand klein. Auf einer Zeitskala, die so gewaehlt ist, dass der Prozess Markovsch ist, passieren diese Spruenge "ploetzlich". Das heißt: Uebergänge zwischen metastabilen Zuständen im Gleichgewicht passieren in einem oder in sehr wenigen Zeitschritten. Mit den vorgestellten Verfahren laesst sich insbesondere die Frage, wie metastabile Zustaende anhand kinetischer Muster zu unsterscheiden sind, behandeln. Die lokale Dynamik wird entweder duch einen raeumlich diskreten Markovschen Sprungprozess oder aber durch einen kontinuierlichen Diffusionsprozess modelliert. Diese beiden Konzepte wurden anhand von Beispielen diskutiert. Insbesondere die Frage der Generatorschaetzung wurde in dieser Arbeit eingehend behandelt. Die Kombination der Generatorschaetzung mit dem Konzept des Hidden Markov Modells ist neu. Sie ermoeglicht die Analyse zeit-kontinuierlicher Prozesse mit bewährten HMM-Techniken. Die Darstellung durch zeit-kontinuierliche Modelle erlaubt insbesondere die Analyse von Zeitreihen mit unterschiedlicher Zeitschrittweite. Desweiteren hat ein HMM mit beobachtbarem Markovschen Sprungprozess den Vorteil, dass der Prozess allein durch die Generatormatrix bestimmt wird und keine zusaetzliche Annahme ueber die Verteilung der Daten notwendig ist. Darueber hinaus hat sich in den Bespielen gezeigt, dass sich selbst bei groben Boxdiskretisierungen die lokale Dynamik durch ein HMM-MJP noch gut beschreiben laesst. Im Rahmen dieser Arbeit wurde das HMM-MJP auf kleine Systeme angewandt, die von einer Smoluchowski Dynamik, einem diskreten Generator oder einem HMM generiert wurden. Die Algorithmen sind jedoch auf den hochdimensionalen Fall uebertragbar. Wie sich das HMM-MJP in der Anwendung auf groeßere Systeme - etwa der Simulation von Biomoleküulen - bewaehrt, ist noch in weiterfuehrenden Arbeiten zu untersuchen. Die Schwierigkeiten, die groeßere Systeme mit sich bringen, sind zum einen der Rechenaufwand und zum anderen die Häufung sehr kleiner Einträge in der Generatormatix, die zu numerischer Instabilitaet fuehren koennen. Ein Ansatz, diese Probleme zu bewaeltigen, ist die Einschränkung des Zustandsraumes, wie in den Beispielen 7.2.5 und 7.2.6 beschrieben.