Organized by P.M. Pardalos, D. Shalloway and G. Xue
Monday, March 20, 1995
08:50--09:00 Welcome from the DIMACS Director and the Organizers
09:00--10:00 Keynote Speach
Herbert Hauptman (Nobel Laureate in Chemistry)
A Minimum Principle in the Phase Problem of X-ray Crystallography
10:00--10:15 Break
Session M.A Chairman: P. Pardalos
10:15--10:45 Klaus Schulten
Simulation of Supramolecular Structures And Dynamics
10:45--11:15 Tamar Schlick
Simulating the Dynamics of Biomolecules
11:15--11:45 Robert E. Bruccoleri
Conformational Search and Protein Modeling
11:45--01:15 LUNCH
Session M.B Chairman: D. Shalloway
01:15--01:45 Wang, Z, Lupo, J., Gates, G., and Pachter, R.
The Design of Chromophore Containing Biomolecules
01:45--02:15 Jeff Skolnick
A Hierarchical Approach to the Prediction of Protein Structure
02:15--02:45 M. M. Zacharias and D. G. Vlachos
Simulated Annealing Calculations of Nanoclusters
02:45--03:00 Break
Session M.C Chairman: G. Xue
03:00--03:30 C.D. Maranas, I.A. Androulakis and C.A. Floudas
A Deterministic Global Optimization Approach for the Protein
Folding Problem
03:30--04:00 R. Byrd, E. Eskow, R. Schnabel, A. van der Hoek
Global Optimization Methods for Protein Folding Problems
04:00--04:30 A.T. Phillips and J.B. Rosen
Molecular Structure Determination by Convex Global
Underestimation of Local Energy Minima
04:30--05:00 Guoliang Xue, Alan Zall and Panos Pardalos
Rapid Evaluation of Potential Energy Functions in Molecular
And Protein Conformations
Tuesday, March 21, 1995
Session T.A Chairman: D. Shalloway
08:45--09:30 Harold A. Scheraga
Computational Problems in Protein Folding
09:30--10:00 Jarek Kostrowicki
Diffusion Equation Method for Conformation Analysis of Molecules
10:00--10:15 Break
Session T.B Chairman: P. Pardalos
10:15--10:45 John E. Straub
Simulated annealing using the classical density distribution
10:45--11:15 Zhijun Wu
Parallel Continuation-Based Global Optimization for Molecular
Conformation and Protein Folding
11:15--11:45 Bruce Church, Matej Oresic and David Shalloway
Tracking Metastable States to Free Energy Global Minima
11:45--01:15 LUNCH
Session T.C Chairman: G. Xue
01:15--01:45 David M. Gay
Automatic Conversion of Algebraically Defined Optimization
Problems to a Representation Designed for Global Optimization
01:45--02:15 Rick Lathrop
Global Optimization and the Detailed Energy Fitness Landscape
in the Threading Approach to Inverse Protein Folding
02:15--02:45 Victor Korotkich
Structural Complexity Approach to Molecular Conformation
And Related Topics in Global Optimization
02:45--03:15 Andrej Sali, Eugene Shakhnovich, and Martin Karplus
Thermodynamics and kinetics of protein folding from lattice
Monte Carlo simulations
03:15--03:45 Jun Gu and Bin Du
A Multispace Search Algorithm for Molecular Energy Minimization
03:45--04:15 P.M. Pardalos and Guoliang Xue
Distance Geometry in Molecular Conformation Problems
04:15--05:00 Discussion and Closing Remarks from the Organizers
A Minimal Principle in the Phase Problem of X-Ray Crystallography
Herbert Hauptman
Medical Foundation of Buffalo, Inc.,
73 High Street, Buffalo, New York 14203-1196
ABSTRACT
The intensities of a sufficient number of X-ray diffraction maxima determine
the structure of a crystal. The available intensities usually exceed the
number of parameters needed to describe the structure. From these intensities
a set of NUMBERS $|E_H|$ can be derived, one corresponding to each intensity.
However, the elucidation of the crystal structure also requires a knowledge
of the complex numbers $E_{H} = |E_{H}| exp (i \phi_{H})$, the normalized
structure factors, of which only the magnitudes $|E_{H}|$ can be determined
from experiment. Thus, a "phase" $\phi_{H}$, unobtainable from the diffraction
experiment, must be assigned to each $|E_{H}|$, and the problem of determining
the phases when only the magnitudes $|E_{H}|$ are known is called the
"phase problem".
Owing to the known atomicity of crystal structures and the redundancy of
observed magnitudes $|E_{H}|$, the phase problem is solvable in principle.
The phase problem may be formulated as one in constrained global optimization.
A method for avoiding the countless minima in order to arrive at the global
minimum will be described.
***************************************************************************
Simulation of Supramolecular Structures and Dynamics
Klaus Schulten
Beckman Institute and Department of Physics,
University of Illinois, Urbana-Champaign
ABSTRACT
The advance of computational algorithms, e.g., multipole and multiple time
scale algorithms, and of parallel computers, e.g., clusters of high end
workstations coupled through fiber optic switches, allow today simulations of
biopolymer systems of 100,000 atoms and more. This allowed us to apply
molecular dynamics simulations to an important frontier of molecular biology,
the study of biomolecular assemblies (supramolecules). The lecture will report
the computational advances and address structures in which complexes of
biopolymer form the smallest functional unit: complexes of proteins with
single and double stranded DNA, the complex of phopholipase A2 with a
biological membrane, the formation of the helical F-actin from G-actin
monomers.
***************************************************************************
Simulating the Dynamics of Biomolecules
Tamar Schlick
Courant Institute and Chemistry Department,
New York University, schlick@nyu.edu
ABSTRACT
The importance of biomolecular modeling and simulations
is steadily increasing with progress in experimental techniques,
algorithm development, and new computing technologies.
One of the major problems in the field involves inadequate
configurational sampling.
In theory, molecular dynamics simulations --- in which atomic motion
is propagated through numerical integration of the classical
equations of motion --- can bridge the spatial and
temporal resolution and thus capture molecular motion over
a wide range of thermally accessible states.
In practice, typical all-atom models and standard integration
methods limit our trajectories to short-time processes
compared to the motion of major interest (e.g., protein folding).
To achieve both numerical stability at large timesteps,
we combine implicit-integration and normal-mode techniques. We also use
macroscopic models in some cases to focus on large-scale, global processes.
Supercoiled DNA, a very compact folded
form of the double helix involving
bending and twisting about the double-helical axis itself,
provides an interesting application system.
In our macroscopic model, the DNA is represented by
a cubic B-spline curve and governed by
elastic and electrostatic potentials. Simulations
reveal distinct families of interwound
supercoiled structures, interesting buckling transitions
between them, dramatic dependency of structure on the salt
environment, and characteristic large-scale motions
(e.g., bending and twisting). Such information provides
valuable insight into key biological processes involving DNA.
***************************************************************************
Conformational Search and Protein Modeling
Robert E. Bruccoleri
Bristol-Myers Squibb ,Pharmaceutical Research Institute,
Room H.3812C, Route 206 and Province Line Road, P.O. Box 4000,
Princeton, NJ 08543
ABSTRACT
Systematic conformational search is a powerful tool in the modeling of
proteins and peptides. As a deterministic method for sampling
comformational space, it provides an efficient mechanism for finding
global energy minima. The program CONGEN has been developed to use
conformational search in conjunction with other modeling methods. The
search operators in CONGEN can be combined in arbitrary ways, and
therefore, they can applied to a wide variety of problems. Typical
applications include homology modeling, construction of protein
coordinates from alpha-carbon positions, sidechain placement,
peptide structure modeling, derivation of three-dimensional structure
from NMR constraints, etc.
In my presentation, I will describe the conformational search
methodology, its applications to protein modeling, and progress in
improving the searching process including a description of its
implementation on shared memory parallel computers.
**************************************************************************
The Design of Chromophore Containing Biomolecules
Wang, Z., Lupo, J., Gates, G. and R. Pachter
Materials Directorate, Wright Laboratory, WL/MLPJ Bldg 651,
3005 P St. Ste. 1, Wright-Patterson AFB, OH 45433-7702,
pachterr@ml.wpafb.af.mil
ABSTRACT
In this study we present a combination of approaches for structure and
properties prediction of polypeptide-bound chromophores to be used in the
design of an ordered three-dimensional network of biopolymers with
controlled nonlinear optical properties. An integrated computational
approach is first applied, consisting of neural networks, and the
double-iterated Kalman Filter (DIKF) technique. Specifically, a neural
network learns to predict the spatial proximity of C-alpha atoms, while the
DIKF algorithm is employed to elucidate the structure using a data set that
includes these pairwise atomic distances, and the distances and angles that
define the chemistry and stereochemistry of the amino acids sequence. This
approach is well suited for this application since it takes into account
the structural uncertainty of the data. The results for test cases,
particularly Crambin and BPTI, demonstrate that such an integrated approach
is useful for the prediction of protein folds at an intermediate
resolution. Refinement is being achieved by applying the adaptive
simulated annealing (ASA) (L. Ingber, Mathl. Comp. Modeling, 12, 967-973
(1989)) approach and genetic algorithms (GA). Results for model peptides
and polypeptide-bound chromophores, as well as for the refinement of
intermediate structures of larger proteins, indicate that ASA is a robust
and efficient algorithm. In addition, the application of GA's offers
significant speedup because of its inherent parallelizability. Finally,
detailed effects of the chromophore substitution are studied utilizing
molecular dynamics simulations, particularly parallelized versions of
GROMOS and CHARMM. Results on utilizing the ASA, GA, DIKF, and MD codes
on massively parallel architectures, especially concerning accuracy and
efficiency, is discussed.
****************************************************************************
An Hierachical Approach to the Prediction of Protein Tertiary Structure
Jeffrey Skolnick, Andrzej Kolinski, Charles L. Brooks, III, Adam Godzik
Department of Molecular Biology, The Scripps Research Institute,
10666 N. Torrey Pines Rd., La Jolla, CA 92037
ABSTRACT
A novel hierarchical approach designed to fold proteins using amino
acid sequence information alone and starting from randomly generated,
denatured states has been developed. The method uses lattice descriptions
of increasing resolution to produce unique conformations at the level of
3-4 =C5 root mean square deviation, rms, from native for the backbone atoms.
These conformations provide the set of secondary structure and side chain
contact constraints used in a full atom construction procedure which
ultimately leads to structures at comparable backbone resolution.
Application to the folding of the 60 residue, B domain of staphylococcal
protein A predicts a three helix bundle which is about 2.25 to 3=C5 from the
experimentally determined structure. Application to a designed, monomeric
version of ROP dimer predicts that the native state for this 120 residue
protein is a left turning, four helix bundle. Comparison with the set of
equivalent residues in the ROP dimer crystal structure indicates that they
differ by about 4-5 =C5. Thus, these simulations demonstrate that the
globular protein folding problem can be solved for sequences having simple
native state topologies.
***************************************************************************
Simulated Annealing Calculations of Nanoclusters
M. M. Zacharias and D. G. Vlachos
Department of Chemical Engineering, University of Massachusetts,
Amherst, MA 01003
ABSTRACT
Nanophase materials of atomic dimensions are important in many applications
such as catalysis, microelectronics, atmospheric pollution, and
cluster-assembled materials. The morphology of small clusters can strongly
affect the properties of materials and selectivity of certain heterogeneous
reactions. Determination of the minimum energy cluster structure is a
NP-(nondeterministic polynomial time complete) minimization problem with the
number of possible minima (isomers) increasing at least exponentially with
the cluster size. Heuristic strategies have mostly been used in the past to
solve such problems which result often in metastable states.
Here we present a probabilistic simulated annealing algorithm to determine
structures of clusters consisting of atoms interacting with the Lennard-Jones
potential. Metropolis Monte Carlo simulations are employed to examine the
roles of quenching, initial cluster temperature, and cluster size in the
probabilities of formation of different isomers. We show that for intermediate
quenching rates the initial nucleated configuration of atoms affects strongly
the arrival probability to a certain attractor, and a mixture of many isomers
will experimentally be observed. At sufficiently slow quenching, cluster
isomerization alters the arrival probabilities and therefore the structure
of materials. We have found that the existence of a critical nucleus size
can result in a lack of ergodicity of the conventional Metropolis walk for
certain cluster sizes, and thus, in limitations of the stochastic
minimization. It is shown that the optimum acceptance ratio of atom
displacements is ~0.3, !
and surprisingly, the quenching schedule can strongly affect cluster
isomerization even near absolute zero temperature for certain conditions.
The roles of cluster size, initial annealing temperature, and nature of
interatomic potential in isomer formation are also discussed.
***************************************************************************
A Deterministic Global Optimization Approach for the
Protein Folding Problem
C.D. Maranas, I.A. Androulakis, and C.A. Floudas
Department of Chemical Engineering, Princeton University,
Princeton, N.J. 08544-5263
Author to whom all correspondence should be addressed.
C.A. Floudas, Department of Chemical Engineering,
Princeton University, Princeton, N.J. 08544-5263
ABSTRACT
A deterministic global optimization algorithm is proposed for locating
the global minimum potential energy conformations of polypeptide
chains. The ECEPP/3 detailed potential energy model is utilized to model
the energetics of the atomic interactions. The minimization of the total
potential energy is formulated on an independent set of dihedral angles,
namely the $\phi,\psi,\omega,\chi$ angles in the residues groups and the
$\theta$ angles of the end groups. Based on previous work on the microcluster
and molecular structure determination, a novel procedure for deriving convex
lower bounding functions for the total potential energy function is utilized.
These underestimating functions satisfy a number of important theoretical
properties. A global optimization algorithm is then proposed based on an
efficient partitioning strategy which is guaranteed to attain
$\epsilon$--convergence to the global minimum potential energy conformation
through the solution of a series of nonlinear convex optimization problems.
The proposed approach has been implemented in C, in the program {\bf GLOFOLD}
and provisions have been made to accommodate user specified partitioning of
the dihedral angles into three sets. The first one (global variables),
consists of dihedral angles where branching occurs, typically backbone
$\phi,\psi,\omega$ angles. The second set (local variables) includes the
dihedral variables where branching is not necessary such as $\chi$ angles.
The third set, (fixed variables) includes the dihedral angles for which
there exists sufficient (experimental) evidence for keeping them fixed.
In addition to the capability of {\bf GLOFOLD} to locate the global
minimum total potential energy polypeptide conformation, low energy protein
conformations close to the global minimum one can also be obtained by
exploiting the identification of promising for the presence of local
minimum protein conformations regions in the potential energy hypersurface
through the construction of lower and upper bounds on the solution.
Local optimization approaches can then be utilized to locate these solutions
within tightly bound regions. The inherent parallel nature of the proposed
branch and bound approach is also analyzed. Tailored partitioning schemes
to the particular distributed computing environment (400 node PARAGON machine)
have been developed, that enable more efficient fathoming.
The proposed deterministic global optimization approach has been applied
to a large number of realistic protein folding problems for some of which
better solutions than the ones reported in the literature have been found.
***************************************************************************
Global Optimization Methods for Protein Folding Problems
R. Byrd, E. Eskow, R. Schnabel, A. van der Hoek
Computer Science Department, University of Colorado at Boulder
ABSTRACT
The problem of finding the configuration that a chemical macro-molecule
assumes in nature is naturally posed as finding the lowest minimizer of
the potential energy function of the macro-molecule. These problems are
very challenging global optimization problems. We have been developing
new stochastic/perturbation global optimization methods and applying them
to molecular configuration problems, initially to molecular cluster
problems and more recently to bio-polymers. This talk will discuss the
methods that we have developed for finding the configurations of polymers,
and our computational results to date. The computational results have been
obtained on massively parallel machines, and interesting parallel computing
issues will also be briefly mentioned.
***************************************************************************
Molecular Structure Determination by Convex Global
Underestimation of Local Energy Minima
A.T. Phillips
Computer Science Department, United States Naval Academy,
572 Holloway Road, Annapolis, MD 21402-5002
J.B. Rosen
Department of Computer Science,
University of Minnesota, Minneapolis, MN 55455
ABSTRACT
The determination of a stable molecular structure can often be formulated
in terms of calculating the global (or approximate global) minimum of a
potential energy function. Computing the global minimum of this function
is very difficult because it typically has a very large number of local
minima which may grow exponentially with molecule size. The optimization
method presented involves collecting a large number of conformers, each
attained by finding a local minimum of the potential energy function from
a random starting point. The information from these conformers is then used
to form a convex quadratic global underestimating function for the potential
energy of all known conformers. This underestimator is an L1 approximation
to all known local minima, and is obtained by a linear programming formulation
and solution. The minimum of this underestimator is used to predict the global
minimum for the function, allowing a localized conformer search to be performed
based on the predicted minimum. The new set of conformers generated by the
localized search serves as the basis for another quadratic underestimation
step in an iterative algorithm. This algorithm has been used to determine the
structure of $n$-chain hydrocarbon molecules for $n \le 30$. While it is
estimated that there are $O(3^n)$ local minima for a chain of length $n$,
this method requires $O(n^4)$ computing time on average. It is also shown
that the global minimum potential energy values lie on a concave quadratic
curve for $n\le 30$. This important property permits estimation of the
minimum energy for larger molecules, and also can be used to accelerate the
global minimization algorithm.
***************************************************************************
Rapid Evaluation of Potential Energy Functions in
Molecular And Protein Conformations
Guoliang Xue and Alan Zall
This research was supported in part by the NSF grant ASC9409285,
Department of Computer Science and Electrical Engineering,
College of Engineering of Mathematics, The University of Vermont,
Burlington, VT 05452
Panos Pardalos
Department of Industrial and Systems Engineering, 303 Weil Hall,
University of Florida, Gainesville, FL 32611
ABSTRACT
In computational studies of molecular structures and protein folding,
some potential energy functions need to be computed very often for
different configurations. For a given cluster of $n$ molecules, the
potential energy function usually contains the pairwise Lennard-Jones
term which requires $O(n^2)$ operations and some other terms which
require $O(n)$ operations. We will report computational results
of the Appel algorithm and the fast multipole algorithm and compare
these methods with the conventional $O(n^2)$ time algorithm.
**************************************************************************
Computational Problems in Protein Folding
Harold A. Scheraga
Baker Laboratory of Chemistry, Cornell University
Ithaca, New York 14853-1301
ABSTRACT
Once a polypeptide chain is synthesized, it folds spontaneously (in a
thermodynamic sense) into the three-dimensional structure of a native
protein. Attempts are currently being made to compute this most stable
structure as the one of minimum free energy. The conformational energy is
expressed as a sum over all pair interactions, and the entropy is computed
from the matrix of second derivatives of the conformational energy.
Algorithms are available for minimizing the conformational energy, but they
lead only to the local minimum that is closest to the starting point,
rather than to the global minimum that is required, according to the
thermodynamic hypothesis; this is the so-called multiple-minima problem.
Various procedures have been developed to surmount this problem. Some of
them work efficiently for short linear and cyclic chains, but are not
readily extendible to long chains. These procedures, and their physical
basis will be discussed. In order to treat the longer chains that are
characteristic of globular proteins, a new procedure (the diffusion
equation method) has been introduced; it will be discussed by J.
Kostrowicki. My presentation will be concerned with the general protein
folding problem and with some of the earlier methods to surmount the
multiple-minima problem. Consideration will also be given to the
fundamental statistical-mechanical aspects of the protein folding problem,
e.g., the relative importance of long- and short-range interactions in
determining the native structure and the nature of the folding/unfolding
transition.
***************************************************************************
Diffusion Equation Method for Conformational Analysis of Molecules
Jaroslaw Kostrowicki and Harold A. Scheraga
Baker Laboratory of Chemistry, Cornell University
Ithaca, New York 14853-1301
ABSTRACT
Molecular systems are essentially constrained - bond lengths and bond angles
vary only within a limited range. We adapted the diffusion equation method
for constrained global minimization. The smoothed energy value for a given
geometry on the manifold fed by all states with fixed bond lengths and bond
angles is the solution to the diffusion equation in the linear subspace
tangent to the manifold at this geometry. The method was tested on small
peptides.
****************************************************************************
Simulated Annealing Using the Classical Density Distribution
John E. Straub
Department of Chemistry, Boston University
Boston, Massachusetts 02215
ABSTRACT
Three algorithms for global energy minimization based on the simulated
annealing of the classical density distribution are presented. The first
is based on annealing the classical density distribution directly in
temperature and is the classical analog of imaginary time quantum dynamics.
Another two algorithms are based on the approximate solution of the classical
Liouville equation for the dynamics of a system coupled to a heat bath using
a rigid temperature constraint and Fokker-Planck dynamics. These three
methods are compared with standard simulated annealing based on molecular
dynamics. The results for a series of Lennard-Jones clusters and for a
model heteropolymer demonstrate that by annealing the continuous density
distribution (representing a volume of phase points) the likelihood of
finding the global minimum is dramatically enhanced.
***************************************************************************
Parallel Continuation-Based Global Optimization for
Molecular Conformation and Protein Folding
Zhijun Wu
Mathematics and Computer Science Division,
Argonne National Laboratory
ABSTRACT
This talk presents our recent work on developing parallel algorithms
and software for solving the global minimization problem for molecular
conformation, especially protein folding. Global minimization problems are
difficult to solve especially when the objective functions are
``poorly-behaved'' with many local minimizers such as the energy functions
to be minimized for protein folding. In our approach, to avoid minimizing
directly a ``difficult'' function, a special integral transformation is
introduced to transform the function into a class of gradually deformed,
but ``smoother'' or ``easier'' functions. An optimization procedure is then
applied to the new functions successively, to trace their solutions back
to the original function. The method can be applied to a large class of
nonlinear partially separable functions, and in particular, the energy
functions for molecular conformation and protein folding. The mathematical
theory for the method as a special continuation approach to global
optimization is established. The algorithms with different solution tracing
strategies are developed. Different level parallelism are exploited for the
implementation of the algorithms on massively parallel architectures.
***************************************************************************
Tracking Metastable States to Free Energy Global Minima
Bruce Church, Matej Oresic and David Shalloway
Biophysics Program, Section of Biochemistry, Molecular and Cell Biology,
Cornell University, Ithaca, NY 14853
ABSTRACT
Proteins thermodynamically explore only limited regions of configuration
space when they are annealed to a folded configuration, and it is suspected
that specific ``folding pathways'' exist. We discuss our methods for
analyzing such pathways using a non-equilibrium thermodynamic approach.
We computationally identify potential pathways by tracking the positions
and sizes (in configuration space) of metastable macrostates (packets)
as temperature is reduced. ``Packet conditions,'' derived from the
Smoluchowski equation, provide a computational prescription for identifying
states and their temperature--dependent bifurcations. The resultant state
``trajectory diagrams'' provide a new method for hierarchically
characterizing energy landscapes and determining if global minima can be
found by iterative thermal/spatial averaging methods. Applications of
the methods to global minimization of Lennard-Jones microclusters and
peptides will be discussed.
**************************************************************************
Automatic Conversion of Algebraically Defined Optimization
Problems to a Representation Designed for Global Optimization
David M. Gay
AT&T Bell Laboratories, Murray Hill, New Jersey 07974
ABSTRACT
Arnold Neumaier has devised a representation for nonlinear optimization
problems that is intended for convenient use in a branch-and-bound
algorithm for constrained optimization. We review this form and discuss
automatic conversion of problems stated in an algebraic modeling language
(AMPL) to this form. One important example is the empirical energy function
for proteins: its global minimization is thought to be a key to the protein
folding problem.
****************************************************************************
Global Optimization and the Detailed Energy Fitness
Landscape in the Threading Approach to Inverse Protein Folding
Rick Lathrop
MIT AI Lab, NE 43-795, 545 Technology Square,
Cambridge, MA 02139, rickl@ai.mit.edu
ABSTRACT
We discuss applications and extensions of a novel branch-and-bound
method for performing protein threading (inverse protein folding) with
gapped alignment and empirical amino acid pair potentials (e.g., contact
potentials, potentials of mean force). The method can be used with a
wide variety of protein threading proposals taken from the literature,
and admits variable-length gaps and an arbitrary gap score function. We
show how this basic method can be used to find the global minimum,
enumerate the low-scoring tail of the distribution, find all low-score
local minima, and estimate the distribution partition function, mean,
standard deviation, segment placement probabilities, and support uniform
sampling.
***************************************************************************
Structural Complexity Approach to Molecular Conformation
Problem and Related Topics in Global Optimization
Victor Korotkich
The Computing Center of the Russian Academy of Sciences,
Vavilov str. 40, 117967, Moscow, Russia
e-mail: korot@sms.ccas.msk.su
ABSTRACT
Binary sequence structural complexity(SC) and structural symmetry(SS)
concepts were introduced in an attempt to adequately capture intuitive
notions of complexity and symmetry of structures [1]. The concepts
definitions are based on Euclidean space-time symmetries developed in [2]
and turn out to be intimately interrelated. Quantitatively SC equals
the genus(plus 1) of an associated smooth projective curve and has
topological meaning in terms of a number of handles of a corresponding
Riemann surface. A chaos quantization gives rise to a spectra of structures
$\omega_{i},i=1,2,... $ linear ordered by a degree of SS, the beauty of
which, as an example for $\omega_{5}$, manifests just as much in the
elegance of the Diophantine equations type identities
1^0 + 4^0 + 6^0 + 7^0 + 10^0 + 11^0 + 13^0 + 16^0 =
2^0 + 3^0 + 5^0 + 8^0 + 9^0 +12^0 + 14^0 + 15^0
1^1 + 4^1 + 6^1 + 7^1 + 10^1 + 11^1 + 13^1 + 16^1 =
2^1 + 3^1 + 5^1 + 8^1 + 9^1 +12^1 + 14^1 + 15^1
1^2 + 4^2 + 6^2 + 7^2 + 10^2 + 11^2 + 13^2 + 16^2 =
2^2 + 3^2 + 5^2 + 8^2 + 9^2 +12^2 + 14^2 + 15^2
1^3 + 4^3 + 6^3 + 7^3 + 10^3 + 11^3 + 13^3 + 16^3 =
2^3 + 3^3 + 5^3 + 8^3 + 9^3 +12^3 + 14^3 + 15^3
In the paper we introduce and discuss SC and SS concepts of a molecular
conformation given by energetics of the interactions between the composing
atoms. We conjecture maximum SC and SS principles connecting stable
conformations of a molecule with a proper quantified by SC and SS structures
spectra. A development of the approach leads to a setting up global
optimization problems to be considered as in [3],[4].
The build-up method [5] and its extensions as self-organizational
processes of complex adaptive systems [6] in terms of SC and SS
are considered.
References
1. V.V. Korotkich, Towards Symbolic Description of Complex
Adaptive Systems Self-Organizational Processes. Notes of the Russian
Academy of Sciences,Technical Cybernetics, N1,1994, pp.20-31.
2. V. Korotkich, Chaos Quantization to Relation Between Algorithm
Optimality and Symmetry. Proceedings of the International Conference
on Dynamical Systems and Chaos, Tokyo, May, 1994, Pergamon Press.
3. P.M. Pardalos, D. Shalloway, G. Xue, Optimization Methods
for Computing Global Optima of Nonconvex Energy Functions,
Journal of Global Optimization, Vol.4, No.2, March 1994, pp.117-133.
4. C.D. Maranas, C.A. Floudas, Global Minimum Potential Energy
Conformations of Small Molecules, Journal of Global Optimization,
Vol.4, No.2, March 1994, pp. 135-170.
5. T. Coleman, D. Shalloway, Z. Wu, A Parallel Build-Up Algorithm
for Global Minimizations of Molecular Clusters Using Effective
Energy Simulated Annealing, Journal of Global Optimization, Vol.4,
No.2, March 1994, pp. 171-185.
6. M. Gell-Mann, The Quark and the Jaguar. Adventures in the
Simple and the Complex, W.H. Freeman and Company, New-York, 1994.
***************************************************************************
Thermodynamics and kinetics of protein folding from
lattice Monte Carlo simulations
Andrej Sali, Eukgene Shakhovich
Rockefeller University, 1230 York Avenue,
New York, NY 10021,
Martin Karplus
Dept. of Chemistry, Harvard University,
12 Oxford St, Cambridge, MA 02138
ABSTRACT
The number of all possible conformations of a polypeptide chain
is too large to be sampled exhaustively. Nevertheless, protein
sequences do fold into unique native states in seconds (Levinthal
paradox). To determine how the Levinthal paradox is resolved, we use a
lattice Monte Carlo model in which the global minimum (native state)
is known. The necessary and sufficient condition for folding in this
model is that the native state be a pronounced global minimum on the
potential surface. This guarantees thermodynamic stability of the
native state at a temperature where the chain does not get trapped in
local minima. Folding starts by a rapid collapse from a random-coil
state to a random semi-compact globule. It then proceeds by a slow,
rate-determining search through the semi-compact states to find a
transition state from which the chain folds rapidly to the native
state. The elements of the folding mechanism that lead to the
resolution of the Levinthal paradox are the reduced number of
conformations that need to be searched in the semi-compact globule
and the existence of many transition states. The results have
evolutionary implications and suggest principles for the folding of
real proteins.
**************************************************************************
A Multispace Search Algorithm for Molecular Energy Minimization
Jun Gu and Bin Du
Dept. of Electrical and Computer Engineering,
University of Calgary, Calgary, Alberta, Canada T2N 1N4,
gu@enel.ucalgary.ca
ABSTRACT
Molecular energy minimization is a challenging problem in molecular
biophysics. Due to numerous local minima in the problem, a traditional
local search algorithm has a tendency to get stuck at a local minimum.
In this work, for Lennard-Jones clusters, we give a multispace search
algorithm for molecular energy minimization. In our approach, along
with local search, structural operations dynamically construct a sequence
of intermediate lattice structures by changing the original lattice
structure. Each intermediate lattice structure is then optimized by
a conjugate gradient method and a pattern search method. Structural
operations disturb the environment of forming local minima, this makes
multispace search a very natural approach to molecular energy minimization.
We will compare the multispace search approach with the local search
algorithm for molecular energy minimization problem.
***************************************************************************
Distance Geometry in Molecular Conformation Problems
P.M. Pardalos
Department of Industrial and Systems Engineering,
303 Weil Hall, University of Florida,
Gainesville, FL 32611
Guoliang Xue
This research was supported in part by the NSF grant ASC9409285,
Department of Computer Science and Electrical Engineering,
College of Engineering of Mathematics,
The University of Vermont, Burlington, VT 05452
ABSTRACT
The potential energy functions that are used in molecular conformation
modeling, are functions of distances between atoms. This special structure
is studied and several properties of the potential functions are proved.
These properties motivate several global optimization approaches for
minimizing nonconvex energy functions.
Previous: Announcement
Next: Registration
Workshop Index
DIMACS Homepage