Program: DIMACS Workshop on Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding

March 20-21, 1995

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


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, 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, 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, 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: 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, 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.

Prev Previous: Announcement
Next Next: Registration
Index Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on February 17, 1995