TY - JOUR A1 - Schmidt-Ehrenberg, Johannes A1 - Baum, Daniel A1 - Hege, Hans-Christian T1 - Visually stunning - Molecular conformations JF - The Biochemist Y1 - 2001 VL - 23 IS - 5 SP - 22 EP - 26 ER - TY - CHAP A1 - Schmidt-Ehrenberg, Johannes A1 - Baum, Daniel A1 - Hege, Hans-Christian ED - J. Moorhead, Robert ED - Gross, Markus ED - I. Joy, Kenneth T1 - Visualizing Dynamic Molecular Conformations T2 - Proceedings of IEEE Visualization 2002 Y1 - 2002 U6 - https://doi.org/10.1109/VISUAL.2002.1183780 SP - 235 EP - 242 PB - IEEE Computer Society Press CY - Boston MA, USA ER - TY - GEN A1 - Baum, Daniel T1 - Finding All Maximal Cliques of a Family of Induced Subgraphs N2 - Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is to find large sets of points satisfying some mutual relationship. This problem can be transformed to the problem of finding all cliques of an undirected graph by mapping each point onto a vertex of the graph and connecting any two vertices by an edge whose corresponding points satisfy our desired relationship. Clique detection has been widely studied and there exist efficient algorithms. In this paper we study a related problem, where all points have a set of binary attributes, each of which is either 0 or 1. This is only a small limitation, since all discrete properties can be mapped onto binary attributes. In our case, we want to find large sets of points not only satisfying some mutual relationship; but, in addition, all points of a set also need to have at least one common attribute with value 1. The problem we described can be mapped onto a set of induced subgraphs, where each subgraph represents a single attribute. For attribute $i$, its associated subgraph contains those vertices corresponding to the points with attribute $i$ set to 1. We introduce the notion of a maximal clique of a family, $\mathcal{G}$, of induced subgraphs of an undirected graph, and show that determining all maximal cliques of $\mathcal{G}$ solves our problem. Furthermore, we present an efficient algorithm to compute all maximal cliques of $\mathcal{G}$. The algorithm we propose is an extension of the widely used Bron-Kerbosch algorithm. T3 - ZIB-Report - 03-53 KW - Bron-Kerbosch algorithm KW - maximal cliques KW - vertex properties KW - family of induced subgraphs KW - backtracking algorithm KW - branch and bound technique KW - re Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7758 ER - TY - GEN A1 - Baum, Daniel T1 - Multiple Semi-flexible 3D Superposition of Drug-sized Molecules N2 - In this paper we describe a new algorithm for multiple semi-flexible superpositioning of drug-sized molecules. The algorithm identifies structural similarities of two or more molecules. When comparing a set of molecules on the basis of their three-dimensional structures, one is faced with two main problems. (1) Molecular structures are not fixed but flexible, i.e., a molecule adopts different forms. To address this problem, we consider a set of conformers per molecule. As conformers we use representatives of conformational ensembles, generated by the program ZIBMol. (2) The degree of similarity may vary considerably among the molecules. This problem is addressed by searching for similar substructures present in arbitrary subsets of the given set of molecules. The algorithm requires to preselect a reference molecule. All molecules are compared to this reference molecule. For this pairwise comparison we use a two-step approach. Clique detection on the correspondence graph of the molecular structures is used to generate start transformations, which are then iteratively improved to compute large common substructures. The results of the pairwise comparisons are efficiently merged using binary matching trees. All common substructures that were found, whether they are common to all or only a few molecules, are ranked according to different criteria, such as number of molecules containing the substructure, size of substructure, and geometric fit. For evaluating the geometric fit, we extend a known scoring function by introducing weights which allow to favor potential pharmacophore points. Despite considering the full atomic information for identifying multiple structural similarities, our algorithm is quite fast. Thus it is well suited as an interactive tool for the exploration of structural similarities of drug-sized molecules. T3 - ZIB-Report - 04-52 KW - pharmaceutical drug design KW - multiple superposition KW - semi-flexible alignment KW - clique detection KW - iterative closest point KW - matching tree Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8278 ER - TY - CHAP A1 - Baum, Daniel T1 - Multiple semi-flexible 3D superposition of drug-sized molecules T2 - Computational Life Sciences: First International Symposium, CompLife 2005 Y1 - 2005 U6 - https://doi.org/10.1007/11560500_18 VL - 3695 SP - 198 EP - 207 PB - Springer CY - Konstanz, Germany ER - TY - CHAP A1 - Baum, Daniel A1 - Hege, Hans-Christian T1 - A Point-matching based algorithm for 3D surface alignment of drug-sized molecules T2 - Computational Life Sciences II, Second International Symposium, CompLife 2006, Cambridge (UK), Sept. 2006 Y1 - 2006 U6 - https://doi.org/10.1007/11875741_18 VL - 4216 SP - 183 EP - 193 PB - Springer ER - TY - THES A1 - Baum, Daniel T1 - A Point-Based Algorithm for Multiple 3D Surface Alignment of Drug-Sized Molecules N2 - One crucial step in virtual drug design is the identification of new lead structures with respect to a pharmacological target molecule. The search for new lead structures is often done with the help of a pharmacophore, which carries the essential structural as well as physico-chemical properties that a molecule needs to have in order to bind to the target molecule. In the absence of the target molecule, such a pharmacophore can be established by comparison of a set of active compounds. In order to identify their common features,a multiple alignment of all or most of the active compounds is necessary. Moreover, since the “outer shape” of the molecules plays a major role in the interaction between drug and target, an alignment algorithm aiming at the identification of common binding properties needs to consider the molecule’s “outer shape”, which can be approximated by the solvent excluded surface. In this thesis, we present a new approach to molecular surface alignment based on a discrete representation of shape as well as physico-chemical properties by points distributed on the solvent excluded surface. We propose a new method to distribute points regularly on a surface w.r.t. a smoothly varying point density given on that surface. Since the point distribution algorithm is not restricted to molecular surfaces, it might also be of interest for other applications. For the computation of pairwise surface alignments, we extend an existing point matching scheme to surface points, and we develop an efficient data structure speeding up the computation by a factor of three. Moreover, we present an approach to compute multiple alignments from pairwise alignments, which is able to handle a large number of surface points. All algorithms are evaluated on two sets of molecules: eight thermolysin inhibitors and seven HIV-1 protease inhibitors. Finally, we compare the results obtained from surface alignment with the results obtained by applying an atom alignment approach. N2 - Die Identifizierung neuer Leitstrukturen (lead structures) zur Entwicklung optimierter Wirkstoffe ist ein äußerst wichtiger Schritt in der virtuellen Wirkstoffentwicklung (virtual drug design). Die Suche nach neuen Leitstrukturen wird oft mit Hilfe eines Pharmakophor-Modells durchgeführt, welches die wichtigsten strukturellen wie auch physiko-chemischen Eigenschaften eines bindenden Moleküls in sich vereint. Ist das Zielmolekül (target) nicht bekannt, kann das Pharmakophor-Modell mit Hilfe des Vergleiches aktiver Moleküle erstellt werden. Hier ist insbesondere die gleichzeitige Überlagerung (multiple alignment) aller oder nahezu aller Moleküle notwendig. Da bei der Interaktion zweier Moleküle die "äußere Form" der Moleküle eine besondere Rolle spielt, sollte diese von jedem Überlagerungsalgorithmus, der sich mit der Identifizierung von Bindungseigenschaften befasst, berücksichtigt werden. Dabei kann die "äußere Form" durch eine bestimmte Art von molekularer Oberfläche approximiert werden, die man als solvent excluded surface bezeichnet. In dieser Arbeit stellen wir einen neuen Ansatz zur Überlagerung molekularer Oberflächen dar, der auf einer diskreten Repräsentation sowohl der Form als auch der molekularen Eigenschaften mittels Punkten beruht. Um die Punkte auf der molekularen Oberfläche möglichst regulär entsprechend einer gegebenen Punktdichte zu verteilen, entwickeln wir eine neue Methode. Diese Methode ist nicht auf Moleküloberflächen beschränkt und könnte daher auch für andere Anwendungen von Interesse sein. Basierend auf einem bekannten Point-Matching Verfahren entwickeln wir einen Point-Matching Algorithmus für Oberflächenpunkte. Dazu erarbeiten wir u.a. eine effiziente Datenstruktur, die den Algorithmus um einen Faktor von drei beschleunigt. Darüberhinaus stellen wir einen Ansatz vor, der Mehrfachüberlagerungen (multiple alignments) aus paarweisen Überlagerungen berechnet. Die Herausforderung besteht hierbei vor allem in der großen Anzahl von Punkten, die berücksichtigt werden muss. Die vorgestellten Algorithmen werden an zwei Gruppen von Molekülen evaluiert, wobei die erste Gruppe aus acht Thermolysin Inhibitoren besteht, die zweite aus sieben HIV-1 Protease Inhibitoren. Darüberhinaus vergleichen wir die Ergebnisse der Oberflächenüberlagerung mit denen einer Atommittelpunktüberlagerung. KW - molecular surface alignment KW - point-based approximation KW - multiple alignment Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-fudissthesis000000002759-2 UR - http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000002759 ER - TY - JOUR A1 - Lindow, Norbert A1 - Baum, Daniel A1 - Prohaska, Steffen A1 - Hege, Hans-Christian T1 - Accelerated Visualization of Dynamic Molecular Surfaces JF - Comput. Graph. Forum Y1 - 2010 U6 - https://doi.org/10.1111/j.1467-8659.2009.01693.x VL - 29 SP - 943 EP - 952 ER - TY - JOUR A1 - Lindow, Norbert A1 - Baum, Daniel A1 - Hege, Hans-Christian T1 - Voronoi-Based Extraction and Visualization of Molecular Paths JF - IEEE Transactions on Visualization and Computer Graphics Y1 - 2011 U6 - https://doi.org/10.1109/TVCG.2011.259 VL - 17 IS - 12 SP - 2025 EP - 2034 ER - TY - CHAP A1 - Homberg, Ulrike A1 - Baum, Daniel A1 - Prohaska, Steffen ED - Mücklich, Frank ED - Slussallek, Philipp ED - Schladitz, Katja T1 - Describing and Analyzing the Dual Structures of Porous Media T2 - Proc. 3D-Microstructure Meeting Y1 - 2011 SP - 24 EP - 25 ER -