DIMACS Workshop on Geometrical Methods for Conformational Modeling: Program

     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