Multi-core CPU or GPU-accelerated Multiscale Modeling for Biomolecular Complexes

Tao Liao ; Yongjie Zhang ; Peter M. Kekenes-Huskey ; Yuhui Cheng ; Anushka Michailova ; Andrew D. McCulloch ; Michael Holst ; J. Andrew McCammon

Molecular Based Mathematical Biology, Tome 1 (2013), p. 164-179 / Harvested from The Polish Digital Mathematics Library

Résumé

Multi-scale modeling plays an important role in understanding the structure and biological functionalities of large biomolecular complexes. In this paper, we present an efficient computational framework to construct multi-scale models from atomic resolution data in the Protein Data Bank (PDB), which is accelerated by multi-core CPU and programmable Graphics Processing Units (GPU). A multi-level summation of Gaussian kernel functions is employed to generate implicit models for biomolecules. The coefficients in the summation are designed as functions of the structure indices, which specify the structures at a certain level and enable a local resolution control on the biomolecular surface. A method called neighboring search is adopted to locate the grid points close to the expected biomolecular surface, and reduce the number of grids to be analyzed. For a specific grid point, a KD-tree or bounding volume hierarchy is applied to search for the atoms contributing to its density computation, and faraway atoms are ignored due to the decay of Gaussian kernel functions. In addition to density map construction, three modes are also employed and compared during mesh generation and quality improvement to generate high quality tetrahedral meshes: CPU sequential, multi-core CPU parallel and GPU parallel. We have applied our algorithm to several large proteins and obtained good results.

Détail

Publié le : 2013-01-01

Zbl 1276.92030

EUDML-ID : urn:eudml:doc:266914

Bibliographie

[1] L. Albou, B. Schwarz, O. Poch, J. Wurtz, and D. Moras. Defining and characterizing protein surface using alpha shapes. Proteins, 76(1):1–12, 2009. [Crossref][PubMed]

[2] S. Artemova, S. Grudinin, and S. Redon. A comparison of neighbor search algorithms for large rigid molecules. Journal of Computational Chemistry, 32(13):2865–2877, 2011. [Crossref]

[3] C. L. Bajaj, J. Castrillon-Candas, V. Siddavanahalli, and Z. Xu. Compressed representations of macromolecular structures and properties. Structure, 13:463–471, 2005. [Crossref][PubMed]

[4] C. L. Bajaj, V. Pascucci, and D. Schikore. Seed sets and search structures for optimal isocontour extraction. Technical report, Texas Institute of Computational and Applied Mathematics, 1999.

[5] C. L. Bajaj, V. Pascucci, A. Shamir, R. J. Holt, and A. N. Netravali. Multiresolution molecular shapes. Technical report, TICAM Technical Report, 1999.

[6] 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. [Crossref] | Zbl 1047.92051

[7] C. L. Bajaj and V. Siddavanahalli. Fast error-bounded surfaces and derivatives computation for volumetric particle data. Technical report, ICES 06-03, 2006.

[8] J. F. Blinn. A generalization of algebraic surface drawing. ACM Transactions on Graphics, 1(3):235–256, 1982. [Crossref]

[9] Y. Cheng, C. A. Chang, Z. Yu, Y. Zhang, M. Sun, T. S. Leyh, M. J. Holst, and J. A. Mccammon. Diffusional channeling in the sulfate activating complex: combined continuum modeling and coarsegrained Brownian dynamics studies. Biophysical Journal, 95(10):4659–4667, 2008. [Crossref]

[10] M. L. Connolly. Analytical molecular surface calculation. Journal of Applied Crystallography, 16(5):548–558, 1983. [Crossref]

[11] M. L. Connolly. Molecular surface: A Review. Network Science, 1996.

[12] J. P. D’Amato and M. Vénere. A CPU-GPU framework for optimizing the quality of large meshes. Journal of Parallel and Distributed Computing, (0):–, 2013.

[13] H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43–72, 1994. [Crossref] | Zbl 0806.68107

[14] R. Fonseca and P. Winter. Bounding volumes for proteins: a comparative study. Journal of Computational Biology, 19(10):1203 – 1213, 2012. [Crossref]

[15] W. Geng and F. Jacob. A GPU-accelerated direct-sum boundary integral Poisson-Boltzmann solver. Computer Physics Communications, 184:1490–1496, 2013. [Crossref] | Zbl 1310.78017

[16] W. Geng and R. Krasny. A treecode-accelerated boundary integral Poisson-Boltzmann solver for electrostatics of solvated biomolecules. Journal of Computational Physics, 247:62–87, 2013. [Crossref]

[17] W. Geng and S. Zhao. Fully implicit ADI schemes for solving the nonlinear Poisson-Boltzmann equation. Molecular Based Mathematical Biology, 1:109–123, 2013. | Zbl 1276.65063

[18] J. Giard and B. Macq. Molecular surface mesh generation by filtering electron density map. International Journal of Biomedical Imaging, pages 263–269, 2010.

[19] J. A. Grant and B. T. Pickup. A Gaussian description of molecular shape. Journal of Physical Chemistry, 99(11):3503– 3510, 1995. [Crossref]

[20] M. Holst, N. Baker, and F. Wang. Adaptive multilevel finite element solution of the Poisson-Boltzmann equation algorithms I: algorithms and examples. Journal of Computational Chemistry, 21:1319–1342, 2000. [Crossref]

[21] L. Hu, D. Chen, and G. Wei. High-order fractional partial differential equation transform for molecular surface construction. Molecular Based Mathematical Biology, 1:1–25, 2013. | Zbl 1277.35338

[22] T. Ju, F. Losasso, S. Schaefer, and J. Warren. Dual contouring of Hermite data. SIGGRAPH, 21:339–346, 2002.

[23] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392, 1998. | Zbl 0915.68129

[24] B. Kim, K. J. Kim, and J. K. Seong. GPU accelerated molecular surface computing. Appl. Math, 6(1S):185S––194S, 2012.

[25] D.-S. Kim, J.-K. Kim, Y Cho, and C.-M. Kim. Querying simplexes in quasi-triangulation. Computer-Aided Design, 44(2):85 – 98, 2012. [Crossref]

[26] D.-S. Kim, J. Seo, D. Kim, J. Ryu, and C.-H. Cho. Three-dimensional beta shapes. Computer-Aided Design, 38(11):1179–1191, 2006. [Crossref]

[27] P. Laug and H. Borouchaki. Molecular surface modeling and meshing. Engineering with Computers, 18:199–210, 2002. [Crossref]

[28] M. S. Lee, M. Feig, F. R. Salsbury, and C. L. Brooks. New analytic approximation to the standard molecular volume definition and its application to generalized born calculations. Journal of Computational Chemistry, 24(14):1348– 1356, 2003. [Crossref]

[29] J. Leng, Y. Zhang, and G. Xu. A novel geometric flow-driven approach for quality improvement of segmented tetrahedral meshes. In Proceedings of the 20th International Meshing Roundtable, pages 347–364, 2012.

[30] W. Li and S. McMains. Voxelized Minkowski sum computation on the GPU with robust culling. Computer-Aided Design, 43(10):1270 – 1283, 2011. [Crossref]

[31] A. Liu and B. Joe. Relationship between tetrahedron shape measures. BIT Numerical Mathematics, 34:268–287, 1994. [Crossref] | Zbl 0806.65104

[32] W. E. Lorensen and H. E. Cline. Marching cubes: a high resolution 3D surface construction algorithm. SIGGRAPH, 21(4):163–169, 1987. [Crossref]

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

[34] B. Lu, X. Cheng, and J. A. McCammon. “New-version-fast-multipole-method" accelerated electrostatic interactions in biomolecular systems. Journal of Computational Physics, 226:1348–1366, 2007. [Crossref] | Zbl 1121.92007

[35] S. Pavanaskar and S. McMains. Filling trim cracks on GPU-rendered solid models. Computer-Aided Design, 45(2):535 – 539, 2013. [Crossref]

[36] J. Ryu, R. Park, and D.-S. Kim. Molecular surfaces on proteins via beta shapes. Computer-Aided Design, 39(12):1042–1057, 2007. [Crossref]

[37] M. F. Sanner, A. J. Olson, and J. C. Spehner. Reduced surface: an efficient way to compute molecular surfaces. Biopolymers, 38(3):305–20, 1996. [Crossref][PubMed]

[38] L. Schmitz, L. F. Scheidegger, D. K. Osmari, C. A. Dietrich, and J. L. D. Comba. Efficient and quality contouring algorithms on the GPU. Computer Graphics Forum, 29:2569 – 2578, 2010. [Crossref]

[39] J.-K. Seong, N. Baek, and K.-J. Kim. Real-time approximation of molecular interaction interfaces based on hierarchical space decomposition. Computer-Aided Design, 43(12):1598 – 1605, 2011. [Crossref]

[40] Y. Song, Y. Zhang, C. L. Bajaj, and N. A. Baker. Continuum diffusion reaction rate calculations of wild-type and mutant mouse acetylcholinesterase: adaptive finite element analysis. Biophysical Journal, 87(3):1558–1566, 2004. [Crossref][PubMed]

[41] Y. Song, Y. Zhang, T. Shen, C. L. Bajaj, J. A. McCammon, and N. A. Baker. Finite element solution of the steady-state Smoluchowksi equation for rate constant calculations. Biophysical Journal, 86(4):2017–2029, 2004. [Crossref][PubMed]

[42] J. E. Stone, D. J. Hardy, I. S. Ufimtsev, and K. Schulten. GPU-accelerated molecular modeling coming of age. Journal of Molecular Graphics and Modelling, 29(2):116 – 125, 2010.

[43] A. Varshney and F. P. Brooks, Jr. Fast analytical computation of richards’s smooth molecular surface. Proceedings of the IEEE Visualization, pages 300–307, 1993.

[44] C. L. Wang and D. Manocha. GPU-based offset surface computation using point samples. Computer-Aided Design, 45(2):321 – 330, 2013. [Crossref]

[45] Q. Wang, J. JaJa, and A. Varshney. An efficient and scalable parallel algorithm for out-of-core isosurface extraction and rendering. Journal of Parallel and Distributed Computing, 67(5):592–603, 2007. [Crossref] | Zbl 1111.68777

[46] G. Wei, Y. Sun, Y. Zhou, and M. Feig. Molecular multiresolution surfaces. arXiv math-ph/0511001, 2005.

[47] Y. Xie, J. Cheng, B. Lu, and L. Zhang. Parallel adaptive finite element algorithms for solving the coupled electrodiffusion equations. Molecular Based Mathematical Biology, 1:90–108, 2013. | Zbl 1276.35143

[48] Z. Yu, Michael J. Holst, Y. Cheng, and J. A. McCammon. Feature-preserving adaptive mesh generation for molecular shape modeling and simulation. Journal of Molecular Graphics and Modeling, 26(8):1370–1380, 2008.

[49] D. Zhang, J. Suen, Y. Zhang, Y. Song, Z. Radic, P. Taylor, M. J. Holst, C. L. Bajaj, N. A. Baker, and J. A. Mc- Cammon. Tetrameric mouse acetylcholinesterase: continuum diffusion rate calculations by solving the steady-state Smoluchowski equation using finite element methods. Biophysical Journal, 88(3):1659–1665, 2005. [PubMed][Crossref]

[50] Y. Zhang, C. L. Bajaj, and B. Sohn. 3D finite element meshing from imaging data. Computer Methods in Applied Mechanics and Engineering, 194(48-49):5083–5106, 2005. [Crossref] | Zbl 1093.65019

[51] Y. Zhang and J. Qian. Resolving topology ambiguity for multiple-material domains. Computer Methods in Applied Mechanics and Engineering, 247–248:166–178, 2012.

[52] Y. Zhang, G. Xu, and C. L. Bajaj. Quality meshing of implicit solvation models of biomolecular structures. Computer Aided Geometric Design, 23(6):510–530, 2006. [Crossref][PubMed] | Zbl 1098.92034

[53] Q. Zheng, S. Yang, and G. Wei. Biomolecular surface construction by PDE transform. International Journal for Numerical Methods in Biomedical Engineering, 28(3):291–316, 2012. | Zbl 1244.92024