More Web Proxy on the site http://driver.im/

research-article

The Molecule Problem: : Exploiting Structure in Global Optimization

Author:

Bruce HendricksonAuthors Info & Claims

SIAM Journal on Optimization, Volume 5, Issue 4

Pages 835 - 857

https://doi.org/10.1137/0805040

Published: 01 November 1995 Publication History

Abstract

The molecule problem is that of determining the relative locations of a set of objects in Euclidean space relying only upon a sparse set of pairwise distance measurements. This NP-hard problem has applications in the determination of molecular conformation. The molecule problem can be naturally expressed as a continuous, global optimization problem, but it also has a rich combinatorial structure. This paper investigates how that structure can be exploited to simplify the optimization problem. In particular, we present a novel divide-and-conquer algorithm in which a large global optimization problem is replaced by a sequence of smaller ones. Since the cost of the optimization can grow exponentially with problem size, this approach holds the promise of a substantial improvement in performance. Our algorithmic development relies upon some recently published results in graph theory. We describe an implementation of this algorithm and report some results of its performance on a sample molecule.

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975x+470

[2]

L. Asimow, B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc., 245 (1978), 279–289

[3]

L. Asimow, B. Roth, The rigidity of graphs. II, J. Math. Anal. Appl., 68 (1979), 171–190

[4]

Richard H. Byrd, Cornelius L. Dert, Alexander H. G. Rinnooy Kan, Robert B. Schnabel, Concurrent stochastic methods for global optimization, Math. Programming, 46 (1990), 1–29

Digital Library

[5]

J. Cheriyan, R. Thurimella, On determining vertex connectivity, Tech. Report, UMIACS-TR-90-79, CS-TR-2485, Dept. of Computer Science, University of Maryland at College Park, 1990

[6]

R. Connelly, 1989, Personal communication, April

[7]

R. Connelly, 1989, Personal communication, September

[8]

Robert Connelly, P. Gritzmann, B. Sturmfels, On generic global rigidityApplied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 4, Amer. Math. Soc., Providence, RI, 1991, 147–155, the Victor Klee Festschrift, ACM

[9]

Henry Crapo, Structural rigidity, Structural Topology, (1979), 26–45, 73

[10]

G. M. Crippen, T. F. Havel, Distance geometry and molecular conformation, Chemometrics Series, Vol. 15, Research Studies Press Ltd., Chichester, 1988x+541

[11]

H. N. Gabow, H. H. Westermann, Forests, frames and games: Algorithms for matroid sums and applications, Proc. 20th Annual Symposium on the Theory of Computing, Chicago, 1988, 407–421

[12]

L. M. Gierasch, J. King, Protein folding: deciphering the second half of the genetic code, AAAS, 1989

[13]

Herman Gluck, Almost all simply connected closed surfaces are rigidGeometric topology (Proc. Conf., Park City, Utah, 1974), Springer, Berlin, 1975, 225–239. Lecture Notes in Math., Vol. 438

[14]

B. Hendrickson, Ph.D. Thesis, The Molecule Problem: Determining Conformation from Pairwise Distances, Cornell University, Dept. of Computer Science, Ithaca, NY, 1990, Technical Report 90-1159

[15]

Bruce Hendrickson, Conditions for unique graph realizations, SIAM J. Comput., 21 (1992), 65–84

Digital Library

[16]

J. E. Hopcroft, R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput., 2 (1973), 135–158

Digital Library

[17]

Hiroshi Imai, On combinatorial structures of line drawings of polyhedra, Discrete Appl. Math., 10 (1985), 79–92

[18]

A. Kanevsky, V. Ramachandran, Improved algorithms for graph four-connectivity, Proc. 28th IEEE Annual Symposium on Foundations of Computer Science, Los Angeles, 1987, 252–259, October

[19]

K. Killian, P. Meissl, Einige grundaufgaben der räumlichen trilateration und ihre gefährlichen örter, Deutsche Geodätische Komm. Bayer. Akad. Wiss., A61 (1969), 65–72

[20]

G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math., 4 (1970), 331–340

[21]

A. V. Levy, A. Montalvo, The tunneling algorithm for the global minimization of functions, SIAM J. Sci. Statist. Comput., 6 (1985), 15–29

Digital Library

[22]

Joseph W. H. Liu, A graph partitioning algorithm by node separators, ACM Trans. Math. Software, 15 (1989), 198–219

Digital Library

[23]

Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis, A unified geometric approach to graph separators32nd Annual Symposium on Foundations of Computer Science (San Juan, PR, 1991), IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 538–547

[24]

J. Moré, D. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput., 4 (1983), 553–572

Digital Library

[25]

K. A. Palmer, 1990, Personal communication, Chemistry Department, Cornell University, Ithaca, NY, March

[26]

K. A. Palmer, H. A. Scheraga, Standard-geometry chains fitted to X-ray derived structures: Validation of the rigid-geometry approximation. ii. systematic searches for short loops in proteins: applications to bovine pancreatic ribonuclease A and human lysozyme, J. Comput. Chem., 13 (1992), 329–350

Digital Library

[27]

A. H. G. Rinnooy Kan, G. T. Timmer, P. Boggs, R. Byrd, R. B. Schnabel, A stochastic approach to global optimizationNumerical optimization, 1984 (Boulder, Colo., 1984), SIAM, Philadelphia, PA, 1985, 245–262

[28]

B. Roth, Rigid and flexible frameworks, Amer. Math. Monthly, 88 (1981), 6–21

[29]

J. B. Saxe, Embeddability of weighted graphs in k-space is strongly NP-hard, Proc. 17th Allerton Conference in Communications, Control and Computing, 1979, 480–489

[30]

P. J. M. van Laarhoven, E. H. L. Aarts, Simulated annealing: theory and applications, Mathematics and its Applications, Vol. 37, D. Reidel Publishing Co., Dordrecht, 1987xii+186

[31]

Walter Wunderlich, Untersuchungen zu einem Trilaterationsproblem mit komplanaren Standpunkten, Österreich. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II, 186 (1977), 263–280

[32]

K. Wütrich, The development of nuclear magnetic resonance spectroscopy as a technique for protein structure determination, Accounts Chemical Res., 22 (1989), 36–44

[33]

K. Wütrich, Protein structure determination in solution by nuclear magnetic resonance spectroscopy, Science, 243 (1989), 45–50

Cited By

Alegría CBorrazzo MDa Lozzo GDi Battista GFrati FPatrignani M(2024)Testing the planar straight-line realizability of 2-trees with prescribed edge lengthsEuropean Journal of Combinatorics10.1016/j.ejc.2023.103806119:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ejc.2023.103806
Carneiro Sde Souza MCardoso DTarrataca LAssis L(2023)A Custom Bio-Inspired Algorithm for the Molecular Distance Geometry ProblemIntelligent Systems10.1007/978-3-031-45368-7_12(178-192)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-45368-7_12

Index Terms

The Molecule Problem: Exploiting Structure in Global Optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Fast Global Optimization of Difficult Lennard-Jones Clusters

The minimization of the potential energy function of Lennard-Jones atomic clusters has attracted much theoretical as well as computational research in recent years. One reason for this is the practical importance of discovering low energy configurations ...
Efficient Algorithms for Large Scale Global Optimization: Lennard-Jones Clusters

A stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of a cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed incorporates within an already ...
Global Optimization on Funneling Landscapes

Molecular conformation problems arising in computational chemistry require the global minimization of a non-convex potential energy function representing the interactions of, for example, the component atoms in a molecular system. Typically the number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 5, Issue 4

Nov 1995

219 pages

ISSN:1052-6234

DOI:10.1137/sjope8.1995.5.issue-4

Issue’s Table of Contents

Copyright © 1995 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 November 1995

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alegría CBorrazzo MDa Lozzo GDi Battista GFrati FPatrignani M(2024)Testing the planar straight-line realizability of 2-trees with prescribed edge lengthsEuropean Journal of Combinatorics10.1016/j.ejc.2023.103806119:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ejc.2023.103806
Carneiro Sde Souza MCardoso DTarrataca LAssis L(2023)A Custom Bio-Inspired Algorithm for the Molecular Distance Geometry ProblemIntelligent Systems10.1007/978-3-031-45368-7_12(178-192)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-45368-7_12

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents