A dynamic data structure for flexible molecular maintenance and informatics

ABSTRACT

We present the "Dynamic Packing Grid" (DPG) data structure along with details of our implementation and performance results, for maintaining and manipulating flexible molecular models and assemblies. DPG can efficiently maintain the molecular surface (e.g., van der Waals surface and the solvent contact surface) under insertion/deletion/movement (i.e., updates) of atoms or groups of atoms. DPG also permits the fast estimation of important molecular properties (e.g., surface area, volume, polarization energy, etc.) that are needed for computing binding affinities in drug design or in molecular dynamics calculations. DPG can additionally be utilized in efficiently maintaining multiple "rigid" domains of dynamic flexible molecules. In DPG, each up-date takes only O (log w) time w.h.p. on a RAM with w-bit words i.e., O (1) time in practice, and hence is extremely fast. DPG's queries include the reporting of all atoms within O (r_max) distance from any given atom center or point in 3-space in O (log log w) (= O (1)) time w.h.p., where r_max is the radius of the largest atom in the molecule. It can also answer whether a given atom is exposed or buried under the surface within the same time bound, and can return the entire molecular surface in O (m) worst-case time, where m is the number of atoms on the surface. The data structure uses space linear in the number of atoms in the molecule.

REFERENCES

• 1: PDB2PQR: An automated pipeline for the setup, execution, and analysis of Poisson-Boltzmann electrostatics calculations. http://pdb2pqr.sourceforge.net/.
• 2: A. A. and W. Z. VRDD: applying virtual reality visualization to protein docking and design. Journal of Molecular Graphics and Modelling, 17(7):180--186, 1999.
• 3: N. Akkiraju and H. Edelsbrunner. Triangulating the surface of a molecule. Discrete Applied Mathematics, 71(1--3):5--22, 1996.
• 4: A. Arkhipov, P. L. Freddolino, K. Imada, K. Namba, and K. Schulten. Coarse-grained molecular dynamics simulations of a rotating bacterial flagellum. Biophy. J., 91:4589--4597, 2006.
• 5: C. Bajaj. A Laguerre Voronoi based scheme for meshing particle systems. Japan Journal of Industrial and Applied Mathematics, 22(2):167--177, June 2005.
• 6: C. Bajaj, H. Y. Lee, R. Merkert, and V. Pascucci. NURBS based B-rep models for macromolecules and their properties. In Proceedings of the 4th ACM Symposium on Solid Modeling and Applications, pages 217--228, New York, NY, USA, 1997. ACM.
• 7: C. Bajaj, V. Pascucci, A. Shamir, R. Holt, and A. Netravali. Multiresolution molecular shapes. Technical report, TICAM, Univ. of Texas at Austin, Dec. 1999.
• 8: C. Bajaj, V. Pascucci, A. Shamir, R. Holt, and A. Netravali. Dynamic maintenance and visualization of molecular surfaces. Dis. App. Math., 127(1):23--51, 2003.
• 9: C. Bajaj and W. Zhao. Fast molecular solvation energetics and forces computation. Technical Report ICES TR-08-20, The University University of Texas at Austin, 2008.
• 10: S. Batsanov. Van der Waals radii of elements. Inorganic Materials, 37:871--885(15), September 2001.
• 11: K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom., 5(2):99--160, 1990.
• 12: M. Connolly. Analytical molecular surface calculation. Journal of Applied Crystallography, 16:548--558, 1983.
• 13: M. Connolly. Solvent-accessible surfaces of proteins and nucleic acids. Science, 221(4612):709--713, 19 August 1983.
• 14: S. Crivelli, O. Kreylos, B. Hamann, N. Max, and W. Bethel. Proteinshop: A tool for interactive protein manipulation and steering. Journal of Computer-Aided Molecular Design, 18(4):271--285, 2004.
• 15: E. Demaine. Advanced data structures (6.897) lecture notes (MIT), Spring 2005. http://courses.csail.mit.edu/6.897/spring05/lec/lec09.pdf.
• 16: B. Duncan and A. Olson. Approximation and characterization of molecular surfaces. Biopolymers, 33(2):219--229, February 1993.
• 17: H. Edelsbrunner and E. Mucke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43--72, 1994.
• 18: M. T. M. Emmerich, J. W. Kruisselbrink, E. van der Horst, A. P. IJzerman, A. Bender, and T. Bäck. Combined interactive and automated adaptive search for molecular design. In Proceedings of Adaptive Computing in Design and Manufacture, 2008.
• 19: E. Eyal and D. Halperin. Dynamic maintenance of molecular surfaces under conformational changes. In SCG '05: Proceedings of the 21st Annual Symposium on Computational Geometry, pages 45--54, New York, NY, USA, 2005. ACM.
• 20: E. Eyal and D. Halperin. Improved maintenance of molecular surfaces using dynamic graph connectivity. Algorithms in Bioinformatics, pages 401--413, 2005.
• 21: M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47(3):424--436, 1993.
• 22: R. A. Gingold and J. J. Monaghan. Smoothed particle hydrodynamics - theory and application to non-spherical stars. Mon. Not. Roy. Astron. Soc., 181:375--389, November 1977.
• 23: J. Grant and B. Pickup. A gaussian description of molecular shape. Journal of Physical Chemistry, 99:3503--3510, 1995.
• 24: D. Halperin and M. H. Overmars. Spheres, molecules, and hidden surface removal. In SCG '94: Proceedings of the 10th Annual Symposium on Computational Geometry, pages 113--122, New York, NY, USA, 1994. ACM.
• 25: R. Hockney and J. Eastwood. Computer Simulation Using Particles. McGraw Hill, 1981.
• 26: W. Humphrey, A. Dalke, and K. Schulten. VMD -- Visual Molecular Dynamics. Journal of Molecular Graphics, 14:33--38, 1996.
• 27: R. M. Jackson, H. A. Gabba, and M. J. E. Sternberg. Rapid refinement of protein interfaces incorporating solvation: application to the docking problem. Journal of Molecular Biology, 276(1):265--285, February 1998.
• 28: O. Kreylos, N. L. Max, B. Hamann, S. N. Crivell, and E. W. Bethel. Interactive protein manipulation. In VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03), page 77, Washington, DC, USA, 2003. IEEE Computer Society.
• 29: J. W. Kruisselbrink, T. Bäck, A. P. IJzerman, and E. van der Horst. Evolutionary algorithms for automated drug design towards target molecule properties. In GECCO '08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pages 1555--1562, New York, NY, USA, 2008. ACM.
• 30: E.-W. Lameijer, J. N. Kok, T. Bäck, and A. P. IJzerman. The molecule evoluator. an interactive evolutionary algorithm for the design of drug-like molecules. Journal of Chemical Information and Modeling, 46(2):545--552, 2006.
• 31: B. Lee and F. Richards. The interpretation of protein structures: estimation of static accessibility. Journal of Molecular Biology, 55(3):379--400, February 1971.
• 32: E. Lindahl and O. Edholm. Mesoscopic undulations and thickness fluctuations in lipid bilayers from molecular dynamics simulations. Biophys. J., 79:426--433, 2000.
• 33: T.-C. Lu, J. Ding, and S. N. Crivelli. DockingShop: a tool for interactive protein docking. In 2005 IEEE Computational Systems Bioinformatics Conference - Workshops, pages 271--272, 2005.
• 34: S. J. Marrink and A. E. Mark. Effect of undulations on surface tension in simulated bilayers. J. Phys. Chem. B, 105:6122--6127, 2001.
• 35: P. G. Mezey. Shape in Chemistry; An introduction to molecular shape and topology. VCH Inc, 1993.
• 36: Y. Modis, S. Ogata, D. Clements, and S. C. Harrison. A ligand-binding pocket in the dengue virus envelope glycoprotein. Proceedings of the National Academy of Sciences, 100(12):6986--6991, 2003.
• 37: C. W. Mortensen, R. Pagh, and M. Pătraçcu. On dynamic range reporting in one dimension. In STOC '05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 104--111, New York, NY, USA, 2005. ACM.
• 38: M. T. Nelson, W. Humphrey, A. Gursoy, A. Dalke, L. V. Kale, R. D. Skeel, and K. Schulten. NAMD: a parallel, object-oriented molecular dynamics program. International Journal of High Performance Computing Applications, 10(4):251--268, 1996.
• 39: R. Pagh and F. Rodler. Cuckoo hashing (C code). http://www.it-c.dk/people/pagh/papers/cuckoo.tar.
• 40: R. Pagh and F. Rodler. Cuckoo hashing. J. Algorithms, 51(2):122--144, 2004.
• 41: J. C. Phillips, R. Braun, W. Wang, J. Gumbart, E. Tajkhorshid, E. Villa, C. Chipot, R. D. Skeel, L. Kalé, and K. Schulten. Scalable molecular dynamics with NAMD. Journal of Computational Chemistry, 26(16):1781--1802, 2005. 10.1002/jcc.20289.
• 42: F. Richards. Areas, volumes, packing, and protein structure. Annual Review of Biophysics and Bioengineering, 6:151--176, June 1977.
• 43: B. Sandak, H. J. Wolfson, and R. Nussinov. Flexible docking allowing induced fit in proteins: insights from an open to closed conformational isomers. Proteins: Structure, Function, and Genetics, 32(2):159--174, December 1998.
• 44: M. Sanner, A. Olson, and J. Spehner. Fast and robust computation of molecular surfaces. In Proceedings of the 11th Annual Symposium on Computational Geometry, pages 406--407. ACM Press, 1995.
• 45: M. Sanner, A. Olson, and J. Spehner. Reduced surface: an efficient way to compute molecular surfaces. Biopolymers, 38(3):305--320, March 1996.
• 46: A. N. Sedwell and I. C. Parmee. Techniques for the design of molecules and combinatorial chemical libraries. In 2007 IEEE Congress on Evolutionary Computation, pages 2435--2442, 2007.
• 47: A. Y. Shih, I. G. Denisov, J. C. Phillips, S. G. Sligar, and K. Schulten. Molecular dynamics simulations of discoidal bilayers assembled from truncated human lipoproteins. Biophys. J., 88:548--556, 2005.
• 48: W. C. Still, A. Tempczyk, R. C. Hawley, and T. Hendrickson. Semianalytical treatment of solvation for molecular mechanics and dynamics. J. Am. Chem. Soc, 112:6127--6129, 1990.
• 49: J. Stone, J. Gullingsrud, P. Grayson, and K. Schulten. A system for interactive molecular dynamics simulation. In J. F. Hughes and C. H. Séquin, editors, 2001 ACM Symposium on Interactive 3D Graphics, pages 191--194, New York, 2001. ACM SIGGRAPH.
• 50: A. Varshney and F. Brooks. Fast analytical computation of Richards's smooth molecular surface. In Proceedings of the 4th Conference on Visualization, pages 300--307, 1993.
• 51: A. Varshney, J. Frederick P. Brooks, and W. V. Wright. Computing smooth molecular surfaces. IEEE Comput. Graph. Appl., 14(5):19--25, 1994.
• 52: M. Vieth, J. D. Hirst, A. Kolinski, and C. L. Brooks III. Assessing energy functions for flexible docking. Journal of Computational Chemistry, 19(14):1612--1622, 1998.
• 53: R. Voorintholt, M. T. Kosters, G. Vegter, G. Vriend, and W. G. Hol. A very fast program for visualizing protein surfaces, channels and cavities. Journal of Molecular Graphics, 7(4):243--245, December 1989.
• 54: D. Willard. Log-logarithmic worst-case range queries are possible in space n. Information Processing Letters, 17(2):81--84, 1983.
• 55: T. You and D. Bashford. An analytical algorithm for the rapid determination of the solvent accessibility of points in a three-dimensional lattice around a solute molecule. Journal of Computational Chemistry, 16(6):743--757, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems; Physically based modeling

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance

Keywords:
de novo drug design, computer aided design, interactive software, molecular docking, protein folding, shape modeling