TY - GEN A1 - Galliat, Tobias A1 - Deuflhard, Peter A1 - Roitzsch, Rainer A1 - Cordes, Frank T1 - Automatic Identification of Metastable Conformations via Self-Organized Neural Networks N2 - 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. T3 - ZIB-Report - 00-51 KW - biochemical conformations KW - cluster analysis KW - Molecular Dynamics KW - Monte-Carlo methods KW - operator discretization KW - Perron cluster Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6197 ER - TY - GEN A1 - Weber, Marcus A1 - Galliat, Tobias T1 - Characterization of Transition States in Conformational Dynamics using Fuzzy Sets N2 - 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. T3 - ZIB-Report - 02-12 KW - biochemical conformations KW - conformational dynamics KW - molecular dynamics KW - cluster analysis KW - transition states KW - fuzzy sets Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6791 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 - Galliat, Tobias A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter T1 - Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification N2 - 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. T3 - ZIB-Report - SC-99-38 KW - Self-Organizing Maps KW - cluster analysis Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4279 ER - TY - GEN A1 - Galliat, Tobias T1 - Clustering Data of Different Information Levels N2 - 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. T3 - ZIB-Report - SC-99-42 KW - cluster analysis KW - Data Mining KW - data preprocessing KW - information theory KW - missing values KW - Self-Organizing Maps KW - similarity measures Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4319 ER - TY - GEN A1 - Galliat, Tobias A1 - Deuflhard, Peter T1 - Adaptive hierarchical cluster analysis by Self-Organizing Box Maps N2 - 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. T3 - ZIB-Report - 00-13 KW - Self-Organizing Maps KW - cluster analysis KW - Voronoi tessellation KW - feature extraction KW - essential dimensions KW - multilevel methods Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5815 ER - TY - CHAP A1 - Galliat, Tobias A1 - Deuflhard, Peter A1 - Roitzsch, Rainer A1 - Cordes, Frank T1 - Automatic identification of metastable conformations via self-organized neural networks T2 - Proceedings of the 3rd International Workshop on Algorithms for Macromolecular Modelling Y1 - 2002 ER - TY - CHAP A1 - Galliat, Tobias A1 - Deuflhard, Peter A1 - Roitzsch, Rainer A1 - Cordes, Frank ED - Schlick, T. ED - Gan, H. T1 - Automatic Identification of Metastable Conformations via Self-Organized Neural Networks T2 - Computational Methods for Macromolecules Y1 - 2002 UR - http://www.zib.de/PaperWeb/abstracts/ZR-00-51 IS - 24 PB - Springer ER - TY - CHAP A1 - Galliat, Tobias A1 - Huisinga, Wilhelm A1 - Deuflhard, Peter ED - H. Bothe, R. T1 - Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification T2 - Neural Computation, ICSC Academic Press Y1 - 2000 SP - 227 EP - 232 ER -