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

Article

Dynamic maintenance of molecular surfaces under conformational changes

Authors:

Dan HalperinAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 45 - 54

https://doi.org/10.1145/1064092.1064102

Published: 06 June 2005 Publication History

Abstract

We present an efficient algorithm for maintaining the boundary and surface area of protein molecules as they undergo conformational changes. We also describe a robust implementation of the algorithm and report on experimental results with our implementation on proteins with hundreds of residues. Our work extends and combines two previous results: (i) controlled perturbation for static molecular surfaces [18], and (ii) data structures for self-collision testing and energy maintenance of proteins that change conformation [26]. As our method keeps a highly accurate representation of the boundary surface and of the voids in the molecule, it can be useful in various applications such as Monte Carlo Simulation or Molecular Dynamics Simulation. In addition we propose and analyze an alternative method for efficiently recalculating the surface area under conformational (and hence topological) changes based on techniques for efficient dynamic maintenance of graph connectivity; initial results of the implementation of this method show great promise.

References

[1]

P. K. Agarwal and M. Sharir. Arrangements and their applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49--119. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[2]

B. J. Alder and T. E. Wainwright. Phase transition for a hard sphere system. J. Chem. Phys., 27:1208--1209, 1957.

[3]

C. L. Bajaj, V. Pascucci, A. Shamir, R. J. Holt, and A. N. Netravali. Dynamic maintenance and visualization of molecular surfaces. Discrete Applied Mathematics, 127(1):23--51, 2003.

Digital Library

[4]

H. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I. Shindyalov, and P. Bourne. The protein data bank. Nucleic Acids Research, 28:235--242, 2000.

[5]

K. Binder and D. Heerman. MCS in Statistical Physics. Springer Verlag, Berlin, 2nd edition, 1992.

[6]

R. Bryant, H. Edelsbrunner, P. Koehl, and M. Levitt. The area derivative of a space-filling diagram. Discrete & Computational Geometry, 32:293--308, 2004.

Digital Library

[7]

H. L. Cheng, T. K. Dey, H. Edelsbrunner, and J. Sullivan. Dynamic skin triangulation. Discrete & Computational Geometry, 25:525--568, 2001.

Digital Library

[8]

M. L. Connolly. Analytical molecular surface calculation. J. of Applied Crystallography, 16:548--558, 1983.

[9]

M. L. Connolly. Solvent-accessible surfaces of proteins and nucleic acids. Science, 221:709--713, 1983.

[10]

J. J. Craig. Introduction to Robotics: Mechanics and Control. Prentice Hall, 3rd edition, 2005.

Digital Library

[11]

H. Edelsbrunner, M. Facello, P. Fu, and J. Liang. Measuring proteins and voids in proteins. Technical report, Department of Computer Science, Hong Kong University of Science and Technology, 1994.

[12]

S. Funke, C. Klein, K. Mehlhorn, and S. Schmitt. Controlled perturbation for Delaunay triangulations. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1047--1056, 2005.

Digital Library

[13]

A. Grosberg and A. Khokhlov. Statistical physics of macromolecules. AIP Press, New York, 1994.

[14]

D. Halperin. Arrangements. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 24, pages 529--562. Chapman & Hall/CRC, 2nd edition, 2004.

[15]

D. Halperin and E. Eyal. Improved implementation of controlled perturbation for arrangements of spheres. Technical Report ECG-TR-363208-01, Tel-Aviv University, 2003.

[16]

D. Halperin and E. Leiserowitz. Controlled perturbation for arrangements of circles. International Journal of Computational Geometry and Applications, 14(4 & 5):277--310, 2004.

[17]

D. Halperin and M. H. Overmars. Spheres, molecules, and hidden surface removal. Computational Geometry: Theory and Applications, 11(2):83--102, 1998.

Digital Library

[18]

D. Halperin and C. R. Shelton. A perturbation scheme for spherical arrangements with application to molecular modeling. Comput. Geom. Theory Appl., 10:273--287, 1998.

Digital Library

[19]

H. Hansmann and Y. Okamoto. New Monte Carlo algorithms for protein folding. Current Opinion in Structural Biology, 9(2):177--183, 1999.

[20]

M. R. Henzinger and V. King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502--516, 1999.

Digital Library

[21]

J. Holm, K. De Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723--760, 2001.

Digital Library

[22]

A. R. Leach. Molecular modeling: Principles and applications. Addison Wesley Longman Limited, 1996.

Digital Library

[23]

B. Lee and F. M. Richards. The interpretation of protein structure: Estimation of static accessibility. J. of Molecular Biology, 55:379--400, 1971.

[24]

S. M. LeGrand and K. M. Merz. Rapid approximation to molecular surface area via the use of boolean logic and lookup tables. Comput. Chem., 14:349--352, 1993.

Digital Library

[25]

I. Lotan. Algorithms Exploiting the Chain Structure of Proteins. PhD thesis, Dept. Comp. Sci., Stanford Uni., 2004.

Digital Library

[26]

I. Lotan, F. Schwarzer, D. Halperin, and J.-C. Latombe. Algorithm and data structures for efficient energy maintenance during Monte Carlo simulation of proteins. Journal of Computational Biology, 11(5):902--932, 2004.

[27]

P. Mezey. Molecular surfaces. In K. B. Lipkowitz and D. B. Boyd, editors, Reviews in Computational Chemistry, volume I, pages 265--294. VCH Publishers, 1990.

[28]

S. Raab. Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. In Proc. 15th ACM Sympos. Comput. Geom., pages 163--172, 1999.

Digital Library

[29]

F. M. Richards. Areas, volumes, packing, and protein structure. Annual Reviews of Biophysics and Bioengineering, 6:151--176, 1977.

[30]

M. F. Sanner and A. J. Olson. Real time surface reconstruction for moving molecular fragments. In Pacific Symposium on Biocomputing '97, Maui, Hawaii, 1997.

[31]

M. F. Sanner, A. J. Olson, and J. C. Spehner. Fast and robust computation of molecular surfaces. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C6--C7, 1995.

Digital Library

[32]

E. Stein, L. Rics, and A. Brünger. Torsion-angle molecular dynamics as a new efficient tool for NMR structure calculation. J. of Magnetic Resonance, 124:154--164, 1997.

[33]

O. V. Tsodikov, M. T. Record, Jr., and Y. V. Sergeev. Novel computer program for fast exact calculation of accessible and molecular surface areas and average surface curvature. J. Computational Chemistry, 23:600--609, 2002.

[34]

A. Varshney, F. P. Brooks Jr., and W. V. Wright. Computing smooth molecular surfaces. IEEE Computer Graphics and Applications, 14:19--25, 1994.

Digital Library

[35]

M. Zhang and L. E. Kavraki. A new method for fast and accurate derivation of molecular conformations. J. of Chemical Information and Computing Sciences, 42:64--70, 2002.

Cited By

Bajaj CChowdhury RRasheed M(2011)A dynamic data structure for flexible molecular maintenance and informaticsBioinformatics10.1093/bioinformatics/btq62727:1(55-62)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1093/bioinformatics/btq627
Halperin D(2010)Controlled perturbation for certified geometric computing with fixed-precision arithmeticProceedings of the Third international congress conference on Mathematical software10.5555/1888390.1888415(92-95)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888390.1888415
Kim DCho YRyu JKim C(2010)Topologies of surfaces on molecules and their computation in O(n) timeComputer-Aided Design10.1016/j.cad.2010.04.00842:9(795-807)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.cad.2010.04.008
Show More Cited By

Index Terms

Dynamic maintenance of molecular surfaces under conformational changes
1. Applied computing
  1. Life and medical sciences
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Structure-based drug design of novel M. tuberculosis InhA inhibitors based on fragment molecular orbital calculations
Abstract
2-trans enoyl-acyl carrier protein reductase (InhA) is a promising target for developing novel chemotherapy agents for tuberculosis, and their inhibitory effects on InhA activity were widely investigated by the physicochemical ...
Graphical abstract
Outline of proposing novel potent InhA inhibitors based on our ab initio molecular simulations based on protein-ligand docking and fragment molecular orbital methods.

Display Omitted
Highlights
- Interactions between 2-trans enoyl-acyl carrier protein and its inhibitors were studied.
Global-to-local representation and visualization of molecular surfaces using deformable models
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

Macromolecules such as proteins and enzymes are responsible for most of cellular functionality. Many molecular interactions, such as protein-protein interactions or protein-ligand binding, occur at what can be defined as the molecular surface. The ...
Kernel modeling for molecular surfaces using a uniform solution

In this paper, a rational Bezier surface is proposed as a uniform approach to modeling all three types of molecular surfaces (MS): the van der Waals surface (vdWS), solvent accessible surface (SAS) and solvent excluded surface (SES). Each molecular ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
320
Total Downloads

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

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bajaj CChowdhury RRasheed M(2011)A dynamic data structure for flexible molecular maintenance and informaticsBioinformatics10.1093/bioinformatics/btq62727:1(55-62)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1093/bioinformatics/btq627
Halperin D(2010)Controlled perturbation for certified geometric computing with fixed-precision arithmeticProceedings of the Third international congress conference on Mathematical software10.5555/1888390.1888415(92-95)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.5555/1888390.1888415
Kim DCho YRyu JKim C(2010)Topologies of surfaces on molecules and their computation in O(n) timeComputer-Aided Design10.1016/j.cad.2010.04.00842:9(795-807)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.cad.2010.04.008
Halperin D(2010)Controlled Perturbation for Certified Geometric Computing with Fixed-Precision ArithmeticMathematical Software – ICMS 201010.1007/978-3-642-15582-6_19(92-95)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15582-6_19
Bajaj CChowdhury RRasheed MBronsvoort WGonsor DRegli WGrandine TVandenbrande JGravesen JKeyser J(2009)A dynamic data structure for flexible molecular maintenance and informatics2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling10.1145/1629255.1629287(259-270)Online publication date: 5-Oct-2009
https://dl.acm.org/doi/10.1145/1629255.1629287
Cazals FLoriot S(2009)Computing the arrangement of circles on a sphere, with applications in structural biologyComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.10.00442:6-7(551-565)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.10.004
de Castro PCazals FLoriot STeillaud M(2009)Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphereComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.10.00342:6-7(536-550)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.10.003
Ryu JPark RCho YSeo JKim D(2007)\beta-shape Based Computation of Blending Surfaces on a MoleculeProceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering10.1109/ISVD.2007.1(189-198)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.1109/ISVD.2007.1
Eyal EHalperin D(2005)Improved maintenance of molecular surfaces using dynamic graph connectivityProceedings of the 5th International conference on Algorithms in Bioinformatics10.1007/11557067_33(401-413)Online publication date: 3-Oct-2005
https://dl.acm.org/doi/10.1007/11557067_33

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents