LRS -- Lee-Richards Surfaces

	Lee-Richards Surfaces
Work funded by part under grant EF-0312612 from the National Science Foundation under award EF-0312612 Herbert J. Bernstein with participation by Isaac Awuah Asiamah, Ricky Chachra, Clarice Chigbo, Georgi Darakev, Nikolay Darakev, Peter Ivanov, Parag Jain, Mia Jurjevic, Stavros Louris, Kostadin Mitev, Daniel Osei-Kuffuor, Sagar Pilania, Rohit Tripathi, Vencislav Stanev, Georgi Todorov, Peter Zhivkov Dowling College, Department of Mathematics and Computer Science -- Oakdale, NY 11769, USA
Project Overview
Understanding of so-called molecular surfaces is important in structural biology and in drug design. In 1971, Lee and Richards [Lee, Richards 1971] defined a molecular surface as the surface resulting from rolling a probe sphere on the van der Waals surface of a molecule. The use of such surfaces has proven to be of great value in docking problems and in drug design. Just a few years ago, interactive rendering of the surfaces of several hundred atoms with the best available software strained the then-available hardware. Current software technology for the rendering of molecular surfaces is slightly short of the performance needed for high quality interactive rendering of the largest macromolecules on commonly available graphics workstations. Some of the best available packages in terms of performance are limited in their range of applications (e.g. one package cannot render nucleic acids). Clearly this is the time for an aggressive push to gain the best possible software performance and the best possible coverage. This project aims to provide a modest, but significant, incremental improvement in surface rendering algorithms by trading time for space, by changing dots and triangles to elliptical rendering elements more appropriate to this task, and by embedding an awareness of display resolution in the algorithms used. RasMol 2.7.3 is the latest version of a molecular surfacing package that showcases the ITR project's efforts. The source code is free to the public and precompiled binaries for a number of systems are also available. As of this writing (Aug 2005) the focus has been on accuracy of the rendering of the surface, rather than speed.
Image Gallery	Introduction	Movie Gallery
[view all images]	When using molecular graphics to dock two molecules, as in interactive drug design, it helps to assign a surface to one or both molecules. While not strictly physical, such a surface conveniently limits the extent to which molecules may interpenetrate, helping to estimate key-inlock fits. (See [Dickerson, Geis 1969, p68]). Early surface renderings were done with spacefilling Corey-Pauling-Koltun (CPK) models [Corey, Pauling 1953], creating an implicit surface from the visible exterior of intersecting van der Waals spheres. Such a surface is useful, but has distracting features. Smoother representation of a surface allows better understanding of the fit between molecules. The commonly accepted definition of a such a smoothed molecular surface was provided by Lee and Richards [Lee, Richards 1971]. Lee and Richards defined a molecular surface as the surface resulting from rolling a probe sphere on the van der Waals spheres of a CPK model of the molecule. (See Fig. 1.) The result is a surface that agrees with the CPK model where the van der Waals spheres stick out but replaces the inward pointing sharp crevices of a CPK model with smooth torii and spherical triangles. For a review of the concepts and algorithmic developments related to molecular surfaces from 1971 until 1996 see M. Connolly's review [Connolly 1996]. Calculation of molecular surfaces can be computationally intensive. As interest focuses on larger and larger molecules, questions of efficiency of various approaches to such calculations become important. In [Ivanov et al. 2002] we consider the performance of several recent algorithms for computing molecular surfaces. We recapitulate the essential findings here. Read more...	[view all movies]
Research Plan
As noted above we have initiated a careful review of the structure and performance of existing molecular surface algorithms, and have implemented a preliminary testbed in RasMol to evaluate performance for a wide range of structures with the same code on a variety of platforms. As the PI demonstrated in his work on calculating high precision eigenvalues [Bernstein 1984b], there is a significant difference between theoretical and achievable algorithmic performance. Working within this base we plan to evaluate the performance of cubing versus Voronoi diagrams for the determination of surface bond neighbors. Even though this is a small portion of the total computational effort for rendering a molecular surface, there is no point in wasting time on a less effective algorithm for this step. Properly structured, the time for this step should be slightly worse than O(n) for moderate probe radii. Having obtained a list of bond surface neighbors for each atom by one approach or the other, we will populate bond-surface data structures with the rotation-invariant parameters of the toroidal waist, another O(n) step. At this point we will insert resolution-dependent filtering steps. If, in the current image view, a toroidal waist is less than three pixels wide, it need not be rendered. Those surface bonds may be pruned from the lists, independent of rotation, but dependent on scaling. If, in the current image view, a toroidal waist is off-screen it need not be rendered. Those surface bonds may be pruned from the lists, dependent on scaling, translation and rotation. These are all O(n) or better steps. Read more...
Question and Answer
Why is Real-Time Rendering of Surfaces Important? Why Not Solve the Problem with Hardware? If Sanner's MSMS is the "maximal speed" way to compute molecular surfaces, why is this research needed? If the changes needed are so clear, why is this a three year proposal instead of a six month SGER? Why is 'artistry' important in molecular graphics? All Questions and Answers...
References
[Bernstein et al. 1977] Bernstein, F. C., Koetzle, T. F., Williams, G. J. B., Meyer, E. F. Jr, Brice, M. D., Rodgers, J. R., Kennard, O., Shimanouchi, T., Tasumi, M. (1977) "The Protein Data Bank: a computer-based archival file for macromolecular structures", J. Mol. Biol. 112: 535- 542 [Bernstein 1984a] Bernstein,, H. J. (1984) "Determining the Shape of a Convex n-sided Polygon by using 2n+k Tactile Probes", New York University, Courant Institute of Mathematical Sciences, Technical Report No. 120, Robotics Report No. 29, June 1984, 13 pp., Information Processing Letters, Vol. 22, April 1986, 255-260. [Bernstein 1984b] Bernstein, H. J. (1984) "An Accelerated Bisection Method for the Determination of the Eigenvalues of a Symmetric Tridiagonal Matrix," Numer. Math. 43: 153- 160. [Bernstein 2000] Bernstein, H. J. (2000) "Recent changes to RasMol, recombining the variants, Trends in Biochemical Sciences (TIBS) 25: No. 9, 453-455. [Bernstein, Bernstein 2002] Bernstein, H. J., Bernstein, F. C., (2002) "Extension of RasMol to Display Surfaces, to Handle CML/XML and other new Features" presentation at XIX Congress and General Assembly of the International Union of Crystallography, Geneva, Switzerland, August 6-15, 2002. [Bajaj 2002] Bajaj, C. L. private communication. [Bajaj, et al. 1997] Bajaj, C., Lee, H. Y., Merkert, R., Pascucci, V., (1997) .NURBS based B-rep Models from Macromolecules and their Properties., In Proceedings Fourth Symposium on Solid Modeling and Applications, Atlanta, Georgia, 1997, Hoffmann, C., Bronsvort, W. Eds., ACM Press. 217-228 [Bystroff 2001] Bystroff, C. (2001), "Masker:Improved Solvent Excluded Molecular Surface Area Estimations using Boolean Masks",Protein Engineering (in press). Renesseler Institute of Polytechnic, Troy, NY. [Bystroff 2002] Bystroff, C. (2002) private communication. [Connolly 1983] Connolly, M. L. (1983) "MS: Molecular Surface Program", QCPE Program 429, Quantum Chemistry Program Exchange, Univ. of Indiana, Bloomington, IN http://www.netsci.org/Science/Compchem/feature14.html [Connolly 1996] Connolly, M. L. (1996) "Molecular Surfaces: A Review", http://www.netsci.org/Science/Compchem/feature14.html [Corey, Pauling 1953] Corey, R. B. and L. Pauling (1953) "Molecular models of amino acids, peptides and proteins." Rev. Sci. Instr. 24: 621-627 [Dickerson, Geis 1969] Dickerson, R. E., Geis, I (1969) "The Structure and Action of Proteins", W. A. Benjamin, Menlo Park, CA, 120 pp. [Dodson et al. 1989] Dodson, G.G., Dodson, E.J., Hodgkin, D.C., Isaacs, N.W., Vijayan, M. (1989) .Insulin., PDB entry 4INS. See also Baker, E.N., Blundell, T.L., Cutfield, J.F., Cutfield, S.M., Dodson, E.J., Dodson, G.G., Crowfoot Hodgkin, D.M., Hubbard, R.E., Isaacs, N.W.,Reynolds, C.D., Sakabe, K., Sakabe, N., Vijayan, N.M. (1988) "The Structure Of 2zn Pig Insulin Crystals At 1.5 Angstroms Resolution", Philos. Trans. R. Soc. London, Ser. B 319: p. 441 ff. [Eisenhaber 1995] Eisenhaber, F., Philip Lijnzaad, P., Argos, P., Sander, C. & Scharf, M. (1995) "The Double Cube Lattice Method: Efficient Approaches to Numerical Integration of Surface Area and Volume and to Dot Surface contouring of Molecular Assemblies", Journal of Computational Chemistry, 16: N3, 273-284. [Ferrin, Huang, Jarvis, Langridge 1988] Ferrin, T. E., Huang,C. C., Jarvis, L. E., Langridge, R. (1988) "The MIDAS display system", J. Mol. Graphics 6, 13-27. [Ivanov et al. 2002] Ivanov, P. S., Jain, P., Osei-Kuffuor, D., Stanev, V. S., Tripathi, R., Zhivkov,, P. N., Bernstein, H. J., "Comparison of Recent Algorithms for Computing Molecular Surfaces", in preparation. [Katz, Levinthal 1972] Katz, L., C. Levinthal, C. (1072) "Interactive Computer Graphics and the Representation of Complex Biological Structures", Annual Reviews in Biophysics and Bioengineering, 1: 465-504. [Lee, Richard 1971] Lee, B., Richards, F. M. (1971) "The Interpretation of Protein Structures: Estimation of Static Accessibility", J. Mol. Biol. 55: 379-400. [LeGrand, Merz 1993] LeGrand S. M. & Merz, K. M. J. (1993) "Rapid Approximation to Molecular Surface Area via the Use of Boolean Logic and Look-up Tables", Journal of Computational Chemistry 14: 349-52. [MATLAB 2002] "MATLAB Function Reference: delaunay", http://www.mathworks.com/access/helpdesk/help/techdoc/ref/delaunay.html [Merritt, Bacon 1997] Merritt, E. A., Bacon, D. J. (1997). "Raster3D: Photorealistic Molecular Graphics" Methods in Enzymology 277: 505-524. [Pedretti, Villa, Vistoli 2002] Pedretti, L. Villa, G. Vistoli (2002) "Vega: A Versatile Program to Convert, Handle and Visualize Molecular Structure on windows-based PCs" J. Mol. Graph., 21: 47-49. [Sanner 1995] Sanner, M. F.; Olson, A. J.; Jean-Claude Spehner (1995) "Fast and Robust Computation of Molecular Surfaces", Proc. 11th ACM Symp. Comp. Geom, C6-C7. [Sanner 1996] Sanner, M., Olson, A., Spehner, J.-C. (1996) "Reduced Surface: An Efficient Way to Compute Molecular Surfaces", Biopolymers 38: 305-320. [Sayle, Milner-White 1995] Sayle, Milner-White, E. J. (1995) "RasMol: Biomolecular graphics for all", Trends in Biochemical Sciences (TIBS) 20: No. 9, 374. [Sanner 2002] Sanner M., private communication. [Valadon 2002] Valadon, P. (2002) "RasTop Molecular Visualization Software", http://www.geneinfinity.org/rastop/ [Vorobjev 1997] Vorobjev, Y. N. (1997) "SIMS: Computation of Smooth Invariant Molecular surface", Biophys. J. 73: 722-732
Website Design -- Stavros Louris