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 (2013)

  • Volume: 1, page 164-179
  • ISSN: 2299-3266

Abstract

top
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.

How to cite

top

Tao Liao, et al. "Multi-core CPU or GPU-accelerated Multiscale Modeling for Biomolecular Complexes." Molecular Based Mathematical Biology 1 (2013): 164-179. <http://eudml.org/doc/266914>.

@article{TaoLiao2013,
abstract = {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.},
author = {Tao Liao, Yongjie Zhang, Peter M. Kekenes-Huskey, Yuhui Cheng, Anushka Michailova, Andrew D. McCulloch, Michael Holst, J. Andrew McCammon},
journal = {Molecular Based Mathematical Biology},
keywords = {efficient computation; multi-scale modeling; biomolecular complex; mesh generation; multi-core CPU; GPU},
language = {eng},
pages = {164-179},
title = {Multi-core CPU or GPU-accelerated Multiscale Modeling for Biomolecular Complexes},
url = {http://eudml.org/doc/266914},
volume = {1},
year = {2013},
}

TY - JOUR
AU - Tao Liao
AU - Yongjie Zhang
AU - Peter M. Kekenes-Huskey
AU - Yuhui Cheng
AU - Anushka Michailova
AU - Andrew D. McCulloch
AU - Michael Holst
AU - J. Andrew McCammon
TI - Multi-core CPU or GPU-accelerated Multiscale Modeling for Biomolecular Complexes
JO - Molecular Based Mathematical Biology
PY - 2013
VL - 1
SP - 164
EP - 179
AB - 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.
LA - eng
KW - efficient computation; multi-scale modeling; biomolecular complex; mesh generation; multi-core CPU; GPU
UR - http://eudml.org/doc/266914
ER -

References

top
  1. [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. [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. [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. [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. [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. [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] Zbl1047.92051
  7. [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. [8] J. F. Blinn. A generalization of algebraic surface drawing. ACM Transactions on Graphics, 1(3):235–256, 1982. [Crossref] 
  9. [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. [10] M. L. Connolly. Analytical molecular surface calculation. Journal of Applied Crystallography, 16(5):548–558, 1983. [Crossref] 
  11. [11] M. L. Connolly. Molecular surface: A Review. Network Science, 1996. 
  12. [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. [13] H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43–72, 1994. [Crossref] Zbl0806.68107
  14. [14] R. Fonseca and P. Winter. Bounding volumes for proteins: a comparative study. Journal of Computational Biology, 19(10):1203 – 1213, 2012. [Crossref] 
  15. [15] W. Geng and F. Jacob. A GPU-accelerated direct-sum boundary integral Poisson-Boltzmann solver. Computer Physics Communications, 184:1490–1496, 2013. [Crossref] Zbl1310.78017
  16. [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. [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. Zbl1276.65063
  18. [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. [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. [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. [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. Zbl1277.35338
  22. [22] T. Ju, F. Losasso, S. Schaefer, and J. Warren. Dual contouring of Hermite data. SIGGRAPH, 21:339–346, 2002. 
  23. [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. Zbl0915.68129
  24. [24] B. Kim, K. J. Kim, and J. K. Seong. GPU accelerated molecular surface computing. Appl. Math, 6(1S):185S––194S, 2012. 
  25. [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. [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. [27] P. Laug and H. Borouchaki. Molecular surface modeling and meshing. Engineering with Computers, 18:199–210, 2002. [Crossref] 
  28. [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. [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. [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. [31] A. Liu and B. Joe. Relationship between tetrahedron shape measures. BIT Numerical Mathematics, 34:268–287, 1994. [Crossref] Zbl0806.65104
  32. [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. [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. [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] Zbl1121.92007
  35. [35] S. Pavanaskar and S. McMains. Filling trim cracks on GPU-rendered solid models. Computer-Aided Design, 45(2):535 – 539, 2013. [Crossref] 
  36. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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] Zbl1111.68777
  46. [46] G. Wei, Y. Sun, Y. Zhou, and M. Feig. Molecular multiresolution surfaces. arXiv math-ph/0511001, 2005. 
  47. [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. Zbl1276.35143
  48. [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. [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. [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] Zbl1093.65019
  51. [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. [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] Zbl1098.92034
  53. [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. Zbl1244.92024

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.