379
eng
reportzib
0
1998-12-18
1998-12-18
--
From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods
Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide.
SC-98-36
380
urn:nbn:de:0297-zib-3797
Appeared in: J. Comp. Chemistry 20 (1999) pp. 1760-1774
Wilhelm Huisinga
Christoph Best
Frank Cordes
Rainer Roitzsch
Christof Schütte
ZIB-Report
SC-98-36
eng
uncontrolled
conformational ensemble
eng
uncontrolled
cluster method
eng
uncontrolled
structural and dynamical similarity
eng
uncontrolled
representative
eng
uncontrolled
conformation
eng
uncontrolled
essential degrees of freedom
eng
uncontrolled
transi
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
ZIB Allgemein
Schütte, Christof
https://opus4.kobv.de/opus4-zib/files/379/SC-98-36.ps
https://opus4.kobv.de/opus4-zib/files/379/SC-98-36.pdf
851
eng
reportzib
0
2005-03-14
2005-03-14
--
ZIBgridfree - Adaptive Conformation Analysis with qualified Support of Transition States and Thermodynamic Weights
This paper introduces a new algorithm of conformational analysis based on mesh-free methods as described in [M. Weber. Mehless methods in Conformation Dynamics.(2005)]. The adaptive decomposition of the conformational space by softly limiting functions avoids trapping effects and allows adaptive refinement strategies. These properties of the algorithm makes ZIBgridfree particularly suitable for the complete exploration of high-dimensional conformational space. The adaptive control of the algorithm benefits from the tight integration of molecular simulation and conformational analysis. An emphasized part of the analysis is the Robust Perron Cluster Analysis (PCCA+) based on the work of Peter Deuflhard and Marcus Weber. PCCA+ supports an almost-characteristic cluster definition with an outstanding mapping of transition states. The outcome is expressed by the metastable sets of conformations, their thermodynamic weights and flexibility.
05-17
851
urn:nbn:de:0297-zib-8514
Marcus Weber
Holger Meyer
ZIB-Report
05-17
eng
uncontrolled
Molecular Dynamics
eng
uncontrolled
Meshfree Methods
eng
uncontrolled
Conformation Analysis
eng
uncontrolled
Quality Functions
Informatik, Informationswissenschaft, allgemeine Werke
Dynamical systems in statistical mechanics [See also 82Cxx]
Computational methods in Markov chains [See also 65C40]
Classification and discrimination; cluster analysis [See also 68T10]
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/851/ZR-05-17.pdf
https://opus4.kobv.de/opus4-zib/files/851/ZR-05-17.ps
707
eng
reportzib
0
2002-11-15
2002-11-15
--
Metastable Conformations via successive Perron-Cluster Cluster Analysis of dihedrals
Decomposition of the high dimensional conformational space of bio-molecules into metastable subsets is used for data reduction of long molecular trajectories in order to facilitate chemical analysis and to improve convergence of simulations within these subsets. The metastability is identified by the Perron-cluster cluster analysis of a Markov process that generates the thermodynamic distribution. A necessary prerequisite of this analysis is the discretization of the conformational space. A combinatorial approach via discretization of each degree of freedom will end in the so called ''curse of dimension''. In the following paper we analyze Hybrid Monte Carlo simulations of small, drug-like biomolecules and focus on the dihedral degrees of freedom as indicators of conformational changes. To avoid the ''curse of dimension'', the projection of the underlying Markov operator on each dihedral is analyzed according to its metastability. In each decomposition step of a recursive procedure, those significant dihedrals, which indicate high metastability, are used for further decomposition. The procedure is introduced as part of a hierarchical protocol of simulations at different temperatures. The convergence of simulations within metastable subsets is used as an ''a posteriori'' criterion for a successful identification of metastability. All results are presented with the visualization program AmiraMol.
02-40
708
urn:nbn:de:0297-zib-7074
Frank Cordes
Marcus Weber
Johannes Schmidt-Ehrenberg
ZIB-Report
02-40
eng
uncontrolled
metastability
eng
uncontrolled
Perron-Cluster Cluster Analysis
eng
uncontrolled
curse of dimension
eng
uncontrolled
Hybrid Monte Carlo
eng
uncontrolled
significant dihedrals
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
ZIB Allgemein
Weber, Marcus
MOLVIS
https://opus4.kobv.de/opus4-zib/files/707/ZR-02-40.ps
https://opus4.kobv.de/opus4-zib/files/707/ZR-02-40.pdf
726
eng
reportzib
0
2003-03-06
2003-03-06
--
Improved Perron Cluster Analysis
The problem of clustering data can often be transformed into the problem of finding a hidden block diagonal structure in a stochastic matrix. Deuflhard et al. have proposed an algorithm that state s the number $k$ of clusters and uses the sign structure of $k$ eigenvectors of the stochastic matrix to solve the cluster problem. Recently Weber and Galliat discovered that this system of eigenvectors can easily be transformed into a system of $k$ membership functions or soft characteristic functions describing the clusters. In this article we explain the corresponding cluster algorithm and point out the underlying theory. By means of numerical examples we explain how the grade of membership can be interpreted.
03-04
727
urn:nbn:de:0297-zib-7260
Marcus Weber
ZIB-Report
03-04
eng
uncontrolled
cluster analysis
eng
uncontrolled
stochastic matrices
eng
uncontrolled
almost invariant sets
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/726/ZR-03-04.ps
https://opus4.kobv.de/opus4-zib/files/726/ZR-03-04.pdf
741
eng
reportzib
0
2003-07-01
2003-07-01
--
Robust Perron Cluster Analysis in Conformation Dynamics
The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.
03-19
742
urn:nbn:de:0297-zib-7415
Appeared in : Linear Algebra and Its Applications, Special Issue on Matrices and Mathematical Biology, Vol. 398c, 161-184 (2005)
Peter Deuflhard
Marcus Weber
ZIB-Report
03-19
eng
uncontrolled
Markov chains
eng
uncontrolled
cluster algorithms
eng
uncontrolled
Perron cluster analysis
eng
uncontrolled
conformation dynamics
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Eigenvalues, eigenvectors
Clustering [See also 62D05]
ZIB Allgemein
Deuflhard, Peter
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/741/ZR_03_19_erratum.pdf
https://opus4.kobv.de/opus4-zib/files/741/ZR-03-19.ps
https://opus4.kobv.de/opus4-zib/files/741/ZR-03-19.pdf
778
eng
reportzib
0
2003-12-19
2003-12-19
--
Clustering by using a simplex structure
In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs.
04-03
779
urn:nbn:de:0297-zib-7782
Marcus Weber
ZIB-Report
04-03
eng
uncontrolled
cluster algorithms
eng
uncontrolled
Perron cluster analysis
eng
uncontrolled
stochastic matrices
eng
uncontrolled
bipartite graphs
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Eigenvalues, eigenvectors
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/778/ZR-04-03.ps
https://opus4.kobv.de/opus4-zib/files/778/ZR-04-03.pdf
427
eng
reportzib
0
1999-11-26
1999-11-26
--
Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification
One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included.
SC-99-38
427
urn:nbn:de:0297-zib-4279
Appeared in: Proc. of the 2nd Intern. ICSC Symposium on Neural Computation, ISCS Academic Press 2000
Tobias Galliat
Wilhelm Huisinga
Peter Deuflhard
ZIB-Report
SC-99-38
eng
uncontrolled
Self-Organizing Maps
eng
uncontrolled
cluster analysis
Informatik, Informationswissenschaft, allgemeine Werke
Eigenvalues, singular values, and eigenvectors
Classification and discrimination; cluster analysis [See also 68T10]
Learning and adaptive systems [See also 68Q32, 91E40]
ZIB Allgemein
Deuflhard, Peter
https://opus4.kobv.de/opus4-zib/files/427/SC-99-38.ps
https://opus4.kobv.de/opus4-zib/files/427/SC-99-38.pdf
431
eng
reportzib
0
1999-12-07
1999-12-07
--
Clustering Data of Different Information Levels
For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis.
SC-99-42
431
urn:nbn:de:0297-zib-4319
Tobias Galliat
ZIB-Report
SC-99-42
eng
uncontrolled
cluster analysis
eng
uncontrolled
Data Mining
eng
uncontrolled
data preprocessing
eng
uncontrolled
information theory
eng
uncontrolled
missing values
eng
uncontrolled
Self-Organizing Maps
eng
uncontrolled
similarity measures
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Learning and adaptive systems [See also 68Q32, 91E40]
Measures of information, entropy
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/431/SC-99-42.ps
https://opus4.kobv.de/opus4-zib/files/431/SC-99-42.pdf
876
eng
reportzib
0
2005-09-28
2005-09-28
--
Conformation Kinetics as a Reduced Model for Transition Pathways
The complexity of molecular kinetics can be reduced significantly by a restriction to metastable conformations which are almost invariant sets of molecular dynamical systems. With the Robust Perron Cl uster Analysis PCCA+, developed by Weber and Deuflhard, we have a tool available which can be used to identify these conformations from a transition probability matrix. This method can also be applied to the corresponding transition rate matrix which provides important information concerning transition pathways of single molecules. In the present paper, we explain the relationship between these tw o concepts and the extraction of conformation kinetics from transition rates. Moreover, we show how transition rates can be approximated and conclude with numerical examples.
05-43
876
urn:nbn:de:0297-zib-8763
Susanna Kube
Marcus Weber
ZIB-Report
05-43
eng
uncontrolled
conformation kinetics
eng
uncontrolled
transition rates
eng
uncontrolled
Robust Perron Cluster Analysis
Informatik, Informationswissenschaft, allgemeine Werke
Jump processes
Classification and discrimination; cluster analysis [See also 68T10]
ZIB Allgemein
Röblitz, Susanna
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/876/ZR-05-43.pdf
581
eng
reportzib
0
2000-04-18
2000-04-18
--
Adaptive hierarchical cluster analysis by Self-Organizing Box Maps
The present paper aims at an extension of {\sc Kohonen's} Self-Organizing Map (SOM) algorithm to be called Self-Organizing Box Map (SOBM) algorithm; it generates box codebooks in lieu of point codebooks. Box codebooks just like point codebooks indirectly define a Voronoi tessellation of the input space, so that each codebook vector represents a unique set of points. Each box codebook vector comprises a multi-dimensional interval that approximates the related partition of the Voronoi tessellation. Upon using the automated cluster identification method that has recently been developed by the authors, the codebook vectors can be grouped in such a way that each group represents a point cluster in the input space. Since the clustering usually depends on the size of the SOM, one cannot be sure, whether the clustering comes out to be optimal. Refinement of part of the identified clusters would often improve the results. This paper presents the concept of an adaptive multilevel cluster algorithm that performs such refinements automatically. Moreover the paper introduces a concept of essential dimensions and suggests a method for their identification based on our herein suggested box codebooks. Applications of the algorithm to molecular dynamics will be described in a forthcoming paper.
00-13
582
urn:nbn:de:0297-zib-5815
Tobias Galliat
Peter Deuflhard
ZIB-Report
00-13
eng
uncontrolled
Self-Organizing Maps
eng
uncontrolled
cluster analysis
eng
uncontrolled
Voronoi tessellation
eng
uncontrolled
feature extraction
eng
uncontrolled
essential dimensions
eng
uncontrolled
multilevel methods
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Learning and adaptive systems [See also 68Q32, 91E40]
ZIB Allgemein
Deuflhard, Peter
https://opus4.kobv.de/opus4-zib/files/581/ZR-00-13.ps
https://opus4.kobv.de/opus4-zib/files/581/ZR-00-13.pdf
619
eng
reportzib
0
2000-12-18
2000-12-18
--
Automatic Identification of Metastable Conformations via Self-Organized Neural Networks
As has been shown recently, the identification of metastable chemical conformations leads to a Perron cluster eigenvalue problem for a reversible Markov operator. Naive discretization of this operator would suffer from combinatorial explosion. As a first remedy, a pre-identification of essential degrees of freedom out of the set of torsion angles had been applied up to now. The present paper suggests a different approach based on neural networks: its idea is to discretize the Markov operator via self-organizing (box) maps. The thus obtained box discretization then serves as a prerequisite for the subsequent Perron cluster analysis. Moreover, this approach also permits exploitation of additional structure within embedded simulations. As it turns out, the new method is fully automatic and efficient also in the treatment of biomolecules. This is exemplified by numerical results.
00-51
620
urn:nbn:de:0297-zib-6197
Appeared in: T. Schlick, H. H. Gan (eds.) Computational Methods for Macromolecules : Challenges and Applications. Proc. of the 3rd Int. Workshop on Methods for Macromolecular Modelling, New York 2000. Springer 2002. LNCSE 24, pp. 260-284
Tobias Galliat
Peter Deuflhard
Rainer Roitzsch
Frank Cordes
ZIB-Report
00-51
eng
uncontrolled
biochemical conformations
eng
uncontrolled
cluster analysis
eng
uncontrolled
Molecular Dynamics
eng
uncontrolled
Monte-Carlo methods
eng
uncontrolled
operator discretization
eng
uncontrolled
Perron cluster
Informatik, Informationswissenschaft, allgemeine Werke
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]
Classification and discrimination; cluster analysis [See also 68T10]
Learning and adaptive systems [See also 68Q32, 91E40]
Computational methods
ZIB Allgemein
Deuflhard, Peter
https://opus4.kobv.de/opus4-zib/files/619/ZR-00-51.ps
https://opus4.kobv.de/opus4-zib/files/619/ZR-00-51.pdf
679
eng
reportzib
0
2002-03-15
2002-03-15
--
Characterization of Transition States in Conformational Dynamics using Fuzzy Sets
Recently, a novel approach for the analysis of molecular dynamics on the basis of a transfer operator has been introduced. Therein conformations are considered to be disjoint metastable clusters within position space of a molecule. These clusters are defined by almost invariant characteristic functions that can be computed via {\em Perron Cluster} analysis. The present paper suggests to replace crisp clusters with {\em fuzzy} clusters, i.e. to replace characteristic functions with membership functions. This allows a more sufficient characterization of transiton states between different confor conformations and therefore leads to a better understanding of molecular dynamics. Fur thermore, an indicator for the uniqueness of metastable fuzzy clusters and a fast algorithm for the computation of these clusters are described. Numerical examples are included.
02-12
680
urn:nbn:de:0297-zib-6791
Marcus Weber
Tobias Galliat
ZIB-Report
02-12
eng
uncontrolled
biochemical conformations
eng
uncontrolled
conformational dynamics
eng
uncontrolled
molecular dynamics
eng
uncontrolled
cluster analysis
eng
uncontrolled
transition states
eng
uncontrolled
fuzzy sets
Informatik, Informationswissenschaft, allgemeine Werke
Fuzzy set theory
Classification and discrimination; cluster analysis [See also 68T10]
Computational methods
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/679/ZR-02-12.ps
https://opus4.kobv.de/opus4-zib/files/679/ZR-02-12.pdf
961
eng
reportzib
0
2007-07-23
2007-07-23
--
Conformation-based transition state theory
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.
07-18
961
urn:nbn:de:0297-zib-9612
Marcus Weber
ZIB-Report
07-18
eng
uncontrolled
dynamical systems
eng
uncontrolled
transition state theory
eng
uncontrolled
rare events
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Numerical methods (Monte Carlo, series resummation, etc.) [See also 65-XX, 81T80]
Numerical Mathematics
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/961/ZR_07_18.pdf
1402
eng
habilitation
0
2011-09-15
2011-09-15
2011-07-13
A Subspace Approach to Molecular Markov State Models via a New Infinitesimal Generator
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.
urn:nbn:de:0297-zib-14025
Marcus Weber
Marcus Weber
eng
uncontrolled
Conformation Dynamics
eng
uncontrolled
Molecular Kinetics
eng
uncontrolled
Transition Rates
eng
uncontrolled
Markov State Models
Continuous-time Markov processes on general state spaces
Classification and discrimination; cluster analysis [See also 68T10]
Statistical thermodynamics [See also 80-XX]
Numerical Mathematics
Habilitationen
Computational Molecular Design
Weber, Marcus
Zuse Institute Berlin (ZIB)
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/1402/WeberHabil.pdf
https://opus4.kobv.de/opus4-zib/files/1402/WeberHabil-Titel.pdf
https://opus4.kobv.de/opus4-zib/files/1402/Acknowledgement.pdf
1143
eng
reportzib
0
2009-09-07
2009-09-07
--
A Subspace Approach to Molecular Markov State Models via an Infinitesimal Generator
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.
09-27
1438-0064
1192
urn:nbn:de:0297-zib-11432
Marcus Weber
unknown unknown
ZIB-Report
09-27
deu
uncontrolled
Robuste Perron Cluster Analyse
deu
uncontrolled
Molekülkinetik
deu
uncontrolled
Übergangsraten
eng
uncontrolled
Robust Perron cluster analysis
eng
uncontrolled
molecular kinetics
eng
uncontrolled
transition rates
Mathematik
Continuous-time Markov processes on general state spaces
Classification and discrimination; cluster analysis [See also 68T10]
Statistical thermodynamics [See also 80-XX]
Numerical Mathematics
Computational Molecular Design
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/1143/ZR_09_27_rev.pdf
https://opus4.kobv.de/opus4-zib/files/1143/ZR_09_27.pdf
1024
eng
doctoralthesis
0
2002-12-31
2002-12-31
--
Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps
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.
1047
urn:nbn:de:kobv:188-2002001258
http://www.diss.fu-berlin.de/2002/125/
Tobias Galliat
unknown unknown
Peter Deuflhard
deu
uncontrolled
Biochemical conformations
deu
uncontrolled
cluster analysis
deu
uncontrolled
molecular dynamics
deu
uncontrolled
Perron cluster analysis
deu
uncontrolled
Self-Organizing Maps
eng
uncontrolled
Biochemical conformations
eng
uncontrolled
cluster analysis
eng
uncontrolled
molecular dynamics
eng
uncontrolled
Perron cluster analysis
eng
uncontrolled
Self-Organizing Maps
Mathematik
Classification and discrimination; cluster analysis [See also 68T10]
Dissertationen
Numerical Mathematics
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/1024/Dissertation_TobiasGalliat.pdf
933
eng
reportzib
0
2006-07-06
2006-07-06
--
Stable computation of probability densities for metastable dynamical systems
Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest to apply an aggregation/disaggregation method which only addresses wellconditioned sub-problems and thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples.
06-39
933
urn:nbn:de:0297-zib-9331
Appeared in: SIAM J. Multisc. Mod. Sim. 2007, 6(2), pp. 396-416
Marcus Weber
Lionel Walter
Susanna Kube
Peter Deuflhard
ZIB-Report
06-39
eng
uncontrolled
dynamical systems
eng
uncontrolled
metastability
eng
uncontrolled
molecular conformations
eng
uncontrolled
cluster analysis
eng
uncontrolled
sampling
eng
uncontrolled
aggregation/disaggregation
eng
uncontrolled
domain decomposition
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Eigenvalues, eigenvectors
Numerical methods (Monte Carlo, series resummation, etc.) [See also 65-XX, 81T80]
ZIB Allgemein
Deuflhard, Peter
Röblitz, Susanna
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/933/ZR-06-39.pdf
814
eng
reportzib
0
2004-09-29
2004-09-29
--
Perron Cluster Analysis and Its Connection to Graph Partitioning for Noisy Data
The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.
04-39
815
urn:nbn:de:0297-zib-8140
Marcus Weber
Wasinee Rungsarityotin
Alexander Schliep
ZIB-Report
04-39
eng
uncontrolled
Perron cluster analysis
eng
uncontrolled
spectral graph theory
eng
uncontrolled
clustering
eng
uncontrolled
gene expression
Informatik, Informationswissenschaft, allgemeine Werke
Classification and discrimination; cluster analysis [See also 68T10]
Eigenvalues, eigenvectors
Computational methods
ZIB Allgemein
Weber, Marcus
https://opus4.kobv.de/opus4-zib/files/814/ZR-04-39.ps
https://opus4.kobv.de/opus4-zib/files/814/ZR-04-39.pdf
5458
eng
reportzib
0
--
2015-04-21
--
A Variational Bayesian Algorithm for Clustering of Large and Complex Networks
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.
1438-0064
urn:nbn:de:0297-zib-54588
Christian Tobias Willenbockel
Erlinda Koernig
Christof Schütte
ZIB-Report
15-25
eng
uncontrolled
Clustering
eng
uncontrolled
Variational Bayes EM
eng
uncontrolled
Model Selection,
eng
uncontrolled
Stochastic Block Model
eng
uncontrolled
Networks
eng
uncontrolled
unsupervised classification
Estimation
Classification and discrimination; cluster analysis [See also 68T10]
Numerical Mathematics
Schütte, Christof
ECMath-CH7
https://opus4.kobv.de/opus4-zib/files/5458/ZIB-Report_15-25.pdf
5700
eng
reportzib
0
--
2016-01-11
--
Variational Bayesian Inference and Model Selection for the Stochastic Block Model with Irrelevant Vertices
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.
1438-0064
urn:nbn:de:0297-zib-57003
Christian Tobias Willenbockel
Erlinda Körnig
Christof Schütte
ZIB-Report
16-01
eng
uncontrolled
Clustering
eng
uncontrolled
Variational Bayes EM
eng
uncontrolled
Model Selection,
eng
uncontrolled
Stochastic Block Model
eng
uncontrolled
Networks
eng
uncontrolled
unsupervised classification
eng
uncontrolled
Noise
Estimation
Classification and discrimination; cluster analysis [See also 68T10]
Numerical Mathematics
no-project
https://opus4.kobv.de/opus4-zib/files/5700/ZIB-Report_16-01.pdf
7021
eng
reportzib
0
--
2018-08-24
--
Spectral Clustering for Non-reversible Markov Chains
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.
1438-0064
urn:nbn:de:0297-zib-70218
01.07.2018
Comp. Appl. Math., pp 1-16, https://doi.org/10.1007/s40314-018-0697-0
Konstantin Fackeldey
Konstantin Fackeldey
Alexander Sikorski
Marcus Weber
ZIB-Report
18-48
eng
uncontrolled
spectral clustering
eng
uncontrolled
Markov chain
eng
uncontrolled
Schur decomposition
eng
uncontrolled
non-reversible
Numerical Linear Algebra
Statistical physics, thermodynamics, and nonlinear dynamical systems (see also 02.50.-r Probability theory, stochastic processes, and statistics)
Canonical forms, reductions, classification
Classification and discrimination; cluster analysis [See also 68T10]
Numerical Mathematics
Fackeldey, Konstantin
Weber, Marcus
NonequiMSM
Sikorski, Alexander
https://opus4.kobv.de/opus4-zib/files/7021/GenPCCA_FSW.pdf
5013
eng
reportzib
0
--
2014-05-16
--
SAIMeR: Self-adapted method for the identification of metastable states in real-world time series
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.
1438-0064
urn:nbn:de:0297-zib-50130
Iliusi Vega
Erlinda Körnig
Christof Schütte
Tim Conrad
ZIB-Report
14-16
eng
uncontrolled
time series analysis
eng
uncontrolled
application in statistical physics
eng
uncontrolled
recurrence quantification analysis
eng
uncontrolled
threshold
eng
uncontrolled
metastability
eng
uncontrolled
non-linear dynamics
Time series analysis
Applications in statistical physics
Classification and discrimination; cluster analysis [See also 68T10]
Numerical Mathematics
Visual Data Analysis
Schütte, Christof
Conrad, Tim
Bioinformatics in Medicine
https://opus4.kobv.de/opus4-zib/files/5013/ZIB-Report_14-16.pdf