TY - GEN A1 - Weber, Marcus T1 - A Subspace Approach to Molecular Markov State Models via an Infinitesimal Generator N2 - Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern. T3 - ZIB-Report - 09-27 KW - Robuste Perron Cluster Analyse KW - Molekülkinetik KW - Übergangsraten KW - Robust Perron cluster analysis KW - molecular kinetics KW - transition rates Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11432 SN - 1438-0064 ER - TY - THES A1 - Galliat, Tobias T1 - Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps N2 - Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist, spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen Problemen lassen sich die Objekte als Punkte in einem von den Attributen aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte. Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B. in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen. In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen, das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist, wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben. KW - Biochemical conformations KW - cluster analysis KW - molecular dynamics KW - Perron cluster analysis KW - Self-Organizing Maps KW - Biochemical conformations KW - cluster analysis KW - molecular dynamics KW - Perron cluster analysis KW - Self-Organizing Maps Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-2002001258 ER - TY - GEN A1 - Weber, Marcus T1 - Conformation-based transition state theory N2 - For the treatment of equilibrated molecular systems in a heat bath we propose a transition state theory that is based on conformation dynamics. In general, a set-based discretization of a Markov operator ${\cal P}^\tau$ does not preserve the Markov property. In this article, we propose a discretization method which is based on a Galerkin approach. This discretization method preserves the Markov property of the operator and can be interpreted as a decomposition of the state space into (fuzzy) sets. The conformation-based transition state theory presented here can be seen as a first step in conformation dynamics towards the computation of essential dynamical properties of molecular systems without time-consuming molecular dynamics simulations. T3 - ZIB-Report - 07-18 KW - dynamical systems KW - transition state theory KW - rare events Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9612 ER - TY - THES A1 - Weber, Marcus T1 - A Subspace Approach to Molecular Markov State Models via a New Infinitesimal Generator N2 - Supercomputers can simulate complex molecular systems. However, there is a very large gap between the fastest oscillations of covalent bonds of a molecule and the time-scale of the dominant processes. In order to extract the dominant time-scales and to identify the dominant processes, a clustering of information is needed. This thesis shows that only the subspace-based Robust Perron Cluster Analysis (PCCA+) can solve this problem correctly by the construction of a Markov State Model. PCCA+ allows for time-extrapolation in molecular kinetics. This thesis shows the difference between molecular dynamics and molecular kinetics. Only in the molecular kinetics framework a definition of transition rates is possible. In this context, the existence of an infinitesimal generator of the dynamical processes is discussed. If the existence is assumed, the Theorem of Gauß can be applied in order to compute transition rates efficiently. Molecular dynamics, however, is not able to provide a suitable statistical basis for the determination of the transition pattern. KW - Conformation Dynamics KW - Molecular Kinetics KW - Transition Rates KW - Markov State Models Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14025 ER - TY - GEN A1 - Willenbockel, Christian Tobias A1 - Schütte, Christof T1 - Variational Bayesian Inference and Model Selection for the Stochastic Block Model with Irrelevant Vertices N2 - Real World networks often exhibit a significant number of vertices which are sparsely and irregularly connected to other vertices in the network. For clustering theses networks with a model based algorithm, we propose the Stochastic Block Model with Irrelevant Vertices (SBMIV) for weighted net- works. We propose an original Variational Bayesian Expectation Maximiza- tion inference algorithm for the SBMIV which is an advanced version of our Blockloading algorithm for the Stochastic Block Model. We introduce a model selection criterion for the number of clusters of the SBMIV which is based on the lower variational bound of the model likelihood. We propose a fully Bayesian inference process, based on plausible informative priors, which is independent of other algorithms for preprocessing start values for the cluster assignment of vertices. Our inference methods allow for a multi level identification of irrelevant vertices which are hard to cluster reliably ac- cording to the SBM. We demonstrate that our methods improve on the normal Stochastic Block model by applying it to to Earthquake Networks which are an example of networks with a large number of sparsely and irregularly con- nected vertices. T3 - ZIB-Report - 16-01 KW - Clustering KW - Variational Bayes EM KW - Model Selection, KW - Stochastic Block Model KW - Networks KW - unsupervised classification KW - Noise Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57003 SN - 1438-0064 ER - TY - GEN A1 - Willenbockel, Christian Tobias A1 - Schütte, Christof T1 - A Variational Bayesian Algorithm for Clustering of Large and Complex Networks N2 - We propose the Blockloading algorithm for the clustering of large and complex graphs with tens of thousands of vertices according to a Stochastic Block Model (SBM). Blockloading is based on generalized Variational Bayesian EM (VBEM) schemes and works for weighted and unweighted graphs. Existing Variational (Bayesian) EM methods have to consider each possible number of clusters sepa- rately to determine the optimal number of clusters and are prone to converge to local optima making multiple restarts necessary. These factors impose a severe restriction on the size and complexity of graphs these methods can handle. In con- trast, the Blockloading algorithm restricts restarts to subnetworks in a way that provides error correction of an existing cluster assignment. The number of clusters need not be specified in advance because Blockloading will return it as a result. We show that Blockloading outperforms all other variational methods regarding reliability of the results and computational efficiency. T3 - ZIB-Report - 15-25 KW - Clustering KW - Variational Bayes EM KW - Model Selection, KW - Stochastic Block Model KW - Networks KW - unsupervised classification Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54588 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 - Vega, Iliusi A1 - Schütte, Christof A1 - Conrad, Tim T1 - SAIMeR: Self-adapted method for the identification of metastable states in real-world time series N2 - In the framework of time series analysis with recurrence networks, we introduce SAIMeR, a heuristic self-adapted method that determines the elusive recurrence threshold and identifies metastable states in complex time series. To identify metastable states as well as the transitions between them, we use graph theory concepts and a fuzzy partitioning clustering algorithm. We illustrate SAIMeR by applying it to three real-world time series and show that it is able to identify metastable states in real-world data with noise and missing data points. Finally, we suggest a way to choose the embedding parameters used to construct the state space in which this method is performed, based on the analysis of how the values of these parameters affect two recurrence quantitative measurements: recurrence rate and entropy. T3 - ZIB-Report - 14-16 KW - time series analysis KW - application in statistical physics KW - recurrence quantification analysis KW - threshold KW - metastability KW - non-linear dynamics Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50130 SN - 1438-0064 ER -