Organizers: L. J. Guibas (Stanford) [guibas@cs.stanford.edu] T. F. Havel (Harvard) [havel@ptolemy.med.harvard.edu] August 2-3, 1995 Rutgers University Busch Campus-Piscataway CoRE Bldg., First Floor Lecture Hall PROGRAM Wednesday, 2 August 1995 9:00 - 9:30 am Welcome and Introduction Andras Hajnal (Director of DIMACS) Leonidas Guibas (Stanford University) 9:30 - 10:20 am Chemical Applications of Distance Geometry Tim Havel (Harvard University) 10:20 - 10:50 am Coffee break 10:50 - 11:40 am Linearized Embedding Gordon Crippen (University of Michigan) 12:00 - 1:30 pm Lunch 1:30 - 2:20 pm Computational Methods in Protein Modeling and Simulation Michael Levitt (Stanford University) 2:20 - 3:10 pm On the Definition and the Construction of Pockets in Macromolecules Herbert Edelsbrunner (University of Illinois) 3:10 - 3:30 pm Refreshment break 3:30 - 4:20 pm Fast Updating of Electronegativities during Molecular Simulation John Canny (University of California at Berkeley) 4:20 - 5:30 pm Discussion 6:30 - 8:30 pm Workshop dinner Thursday, 3 August 1995 9:30 - 10:20 am Rigid and Hinge-Bending Matching of 3D Macromolecular Structures by Computer Vision Techniques Ruth Nussinov (Tel Aviv University and NIH) 10:20 - 10:50 am Coffee break 10:50 - 11:40 am Geometric Manipulation of Flexible Ligands Dan Halperin (Stanford University) 12:00 - 1:30 pm Lunch 1:30 - 2:20 pm Sampling Conformation Space with the Alternating Projection Algorithm Tom Hayden (University of Kentucky) 2:20 - 3:10 pm The Configuration Space of Small Equi-angular Polygons in 3-space Bob Connelly (Cornell University) 3:10 - 3:30 pm Refreshment break 3:30 - 4:20 pm Linking DNA Base Sequence to Geometric Information Wilma Olson (Rutgers University) 4:20 - 5:10 pm Topic to be announced Rick Fine (BIOSYM Technologies) =============================================================================== The talk abstracts follow: CHEMICAL APPLICATIONS OF DISTANCE GEOMETRY Timothy F. Havel, Harvard Medical School Distance geometry is a general approach to the computation and analysis of molecular conformation, in which the problems of interest are formulated in terms of constraints on the interatomic distances and chiralities. It has been successfully used for such diverse problems as: (*) Converting 2-D chemical diagrams to 3-D structures. (*) The systematic enumeration of stereo-isomers and conformers. (*) Docking flexible ligands to their receptor proteins. (*) Building protein conformations by homology modeling. (*) Determining protein and nucleic acid structure from NMR data. In this talk we shall introduce the basic concepts, mathematics and algorithms used in distance geometry, and show how they are applied to the above problems. LINEARIZED EMBEDDING Gordon M. Crippen, College of Pharmacy, University of Michigan Linearized embedding is a distance geometry method of conformational analysis assuming fixed valence geometry, rather than treating atoms as arbitrary points linked by distance constraints. The molecule is first converted to a linearized representation, where atom positions are linear polynomials in local coordinate vectors fixed to rigid groups in the molecule. Embedding then centers around calculating allowed metric matrices for the local coordinate vectors. Interatomic distance constraints correspond to linear polynomials in the metric matrix elements, rather than to nonlinear terms in the penalty function used in the standard Embed algorithm. Requiring a three dimensional structure can be expressed as a set of equalities on determinants of 4x4 submatrices of the metric matrix. Correct relative chirality between chiral and prochiral rigid groups of atoms corresponds to equalities on determinants of 3x3 submatrices of the metric matrix. For very simple molecules, this approach leads to an analytical solution of the entire conformation space. For molecules having 10 or fewer rotatable bonds, the conformation space can be explored numerically with more uniform and exhaustive coverage than by the DGEOM program. For larger molecules, solving large numbers of quadratic equations presents difficulties. COMPUTATIONAL METHODS IN PROTEIN MODELING AND SIMULATION Michael Levitt, Department of Structural Biology, Stanford University, First, I will review our work on some of the important computational problems in structural biology. These include structural alignment, threading, homology modeling and molecular dynamics simulations. Each will be explained both from a biological point of view so that it becomes clear why these are relevant problems. Second, I will consider some of the algorithmic issues for each of the examples. I will outline our present methods and try to indicate where there is room for improvement. ON THE DEFINITION AND THE CONSTRUCTION OF POCKETS IN MACROMOLECULES Herbert Edeslbrunner, Computer Science Department, Univesity of Illinois The functionally of a protein is partially determined by the shape it assumes in the folded state. This includes the location and size of identifiable regions in its complement. An attempt is made to formally define pockets as geometric regions in the complement with limited accessibility from the outside. The motivating intuition is a flow field attracted to centers of maximum distance to the spherical balls modeling the atoms of the protein. Pockets can be efficiently constructed and graphically rendered by an algorithm based on Voronoi cells and Delaunay simplices. RIGID AND HINGE-BENDING MATCHING OF 3D MACROMOLECULAR STRUCTURES BY COMPUTER VISION TECHNIQUES Ruth Nussinov, Computer Science/Chemistry Dept., Tel Aviv University The physical principles underlying protein structure and biomolecular recognition are similar. The methodology that we have developed to treat these problems is uniquely suitable to investigate both molecular structures and their associations. The computer-vision based algorithms treat protein structures as collections of unconnected points (atoms) in space. Backbone protein atoms are picked for protein structure studies. Points on protein surfaces are employed for biomolecular recognition. Applications of these approaches to protein structures are expected to yield a wealth of data, providing insights into protein folding and evolution. Application of these methodologies, both rigid-body and hinge-bending, to biomolecular associations and "docking" is expected to aid both in understanding protein-protein recognition, and in rational drug design. Initial results in both applications are promising. Results of searches for sub-structural "motifs" in protein structures and for docking will be presented, and their implications will be outlined. The performance of our protein-protein and protein-drug docking will be shown, and in particular, potential applications will be discussed. This work has been carried out jointly with Haim Wolfson, and with our colleagues and graduate students from the NIH and from Tel Aviv University. GEOMETRIC COMPUTING ABOUT SMALL FLEXIBLE LIGANDS Dan Halperin, Department of Computer Science, Stanford University We will describe ongoing research aimed at offering new geometric tools to help chemists select drug candidates and screen drug data bases. The main goal of this research is to identify three-dimensional invariants (called pharmacophores) in a given collection of ligands (each having 20 to 50 atoms) known to have similar activity. This problem requires computing the low-energy conformations of each ligand and their molecular surfaces. Our research therefore focuses on the following issues: computation and update of molecular surfaces for flexible ligands, conformational search using the kinematic properties of the ligands, and identification of invariants in ligands described each by several possible spatial conformations. SAMPLING CONFORMATION SPACE WITH THE ALTERNATING PROJECTION ALGORITHM Tom Hayden, Mathematics Department, University of Kentucky Computational experience with the Alternating Projection Algorithm in the following areas will be presented. 1) Investigation of Topological Stereoisomerism in the heat stable enterotoxin peptide STh produced by E. coli in humans. 2) The effect of accurate bound information between subchains of four residues on the speed of convergence and the sampling properties of the Alternating Projection Algorithm. 3) The effects on sampling conformation space by efforts to alter or replace metrization. 4) Chirality and planarity strategies to reduce CPU time. The last three areas are investigated for poly L-Alanine. THE CONFIGURATION SPACE OF EQUILATERAL EQUI-ANGULAR POLYGONS IN 3-SPACE Robert Connelly, Mathematics Department, Cornell University We consider the configuration space of of all n-vertex cyclic polygons in space with all edges the same length and all angles between adjacent edges fixed at a particular theta. We define an equivalence relation, by saying that two configurations are equivalent if there is a rigid congruence between them. A basic problem, motivated from chemistry, is to determine the number of components of of this configuration space, especially for n=7 and theta approximately 109.5 degrees. According to Crippen and Havel, experimenting with models suggests that this space has exactly two components, a `chair' confirmation and a `boat' confirmation. As far as we know there is no rigorous proof of this "fact". Our basic result is: For n > 6, n odd, and theta sufficiently large, the configuration space has at most two components, and is a non-singular analytic manifold of dimension n-6. This result basically states that when we restrict the angle theta to be large enough so that polygon exists and is close to being planar, then there are at most two components. For n = 7, there are exactly two components and, for n = 9 at least, it "appears" that there is only one component. When n is even, the configuration space is singular and we identify some of the singular configurations. LINKING DNA BASE SEQUENCE TO GEOMETRIC INFORMATION Wilma K. Olson, Department of Chemistry, Rutgers University One of the major quests of structural biology is unraveling the sequence-dependent rules governing the three-dimensional folding of naturally occurring biopolymers. While the protein folding problem is frequently assumed to be more challenging, extracting the principles that underlie the subtle base sequence-dependent structural features of double helical DNA is equally important. The long DNA chain bends, twists, and stretches in response to base sequence and to specific interactions with the chemical environment. Such heterogeneity (although much less impressive on a local spatial scale than that in proteins) plays a crucial role for all processes involving DNA recognition. Current work in this laboratory focuses on the local base pair parameters that determine the long-range organization and reveal themselves in the overall macroscopic shape of DNA. Specifically, we concentrate on the angular and translational variables between adjacent base pair planes: twist, roll, tilt, shift, slide, rise. Long DNA chains are defined in terms of sequences of virtual bonds that reflect the observed sequence-dependent positioning and fluctuations of base pairs found in the accumulating DNA X-ray crystallographic literature. This information is used to study effects of base sequence on selected properties of linear and spatially constrained polymers.

Previous: Announcement

Next: Registration

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on June 19, 1995