@misc{Weber, author = {Weber, Marcus}, title = {A Subspace Approach to Molecular Markov State Models via an Infinitesimal Generator}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11432}, number = {09-27}, abstract = {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.}, language = {en} } @phdthesis{Galliat, author = {Galliat, Tobias}, title = {Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:188-2002001258}, abstract = {Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bez{\"u}glich eines gegebenen Maßes maximal homogen sind. Die Homogenit{\"a}t der Objekte h{\"a}ngt dabei direkt oder indirekt von den Auspr{\"a}gungen ab, die sie f{\"u}r eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern l{\"a}ß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{\"o}tigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexit{\"a}t. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren f{\"u}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{\"a}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{\"u}len von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen {\"A}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{\"a}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{\"o}rt, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexit{\"a}tsreduktion ohne Zerst{\"o}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{\"o}glicht die einfache Generierung von regelbasierten Clusterbeschreibungen. F{\"u}r einen speziellen Typ von Homogenit{\"a}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{\"o}mmlichen Verfahren, nicht mehr als Eingabeparameter ben{\"o}tigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergest{\"u}tzte Konformationsanalyse großer, f{\"u}r die Praxis relevanter Biomolek{\"u}le durchgef{\"u}hrt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.}, language = {en} } @misc{Weber, author = {Weber, Marcus}, title = {Conformation-based transition state theory}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9612}, number = {07-18}, abstract = {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.}, language = {en} } @phdthesis{Weber, author = {Weber, Marcus}, title = {A Subspace Approach to Molecular Markov State Models via a New Infinitesimal Generator}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14025}, school = {Zuse Institute Berlin (ZIB)}, abstract = {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.}, language = {en} } @misc{WillenbockelSchuette, author = {Willenbockel, Christian Tobias and Sch{\"u}tte, Christof}, title = {Variational Bayesian Inference and Model Selection for the Stochastic Block Model with Irrelevant Vertices}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57003}, abstract = {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.}, language = {en} } @misc{WillenbockelSchuette, author = {Willenbockel, Christian Tobias and Sch{\"u}tte, Christof}, title = {A Variational Bayesian Algorithm for Clustering of Large and Complex Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54588}, abstract = {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.}, language = {en} } @misc{FackeldeySikorskiWeber, author = {Fackeldey, Konstantin and Sikorski, Alexander and Weber, Marcus}, title = {Spectral Clustering for Non-reversible Markov Chains}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70218}, abstract = {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.}, language = {en} } @misc{VegaSchuetteConrad, author = {Vega, Iliusi and Sch{\"u}tte, Christof and Conrad, Tim}, title = {SAIMeR: Self-adapted method for the identification of metastable states in real-world time series}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-50130}, abstract = {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.}, language = {en} }