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

• Autorzy: Tao Liao , Yongjie Zhang , Peter M. Kekenes-Huskey , Yuhui Cheng , Anushka Michailova , Andrew D. McCulloch , Michael Holst , J. Andrew McCammon
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

efficient computation; multi-scale modeling; biomolecular complex; mesh generation; multi-core CPU; GPU

• Wydawca: De Gruyter Open
• Czasopismo: Molecular Based Mathematical Biology
• Rocznik: 2013
• Tom: 1
• Strony: 164-179

Daty

otrzymano

2013-06-04

zaakceptowano

2013-07-09

online

2013-07-19

Twórcy

autor

Tao Liao

autor

Yongjie Zhang,

autor

Peter M. Kekenes-Huskey

autor

Yuhui Cheng

autor

Anushka Michailova

autor

Andrew D. McCulloch

autor

Michael Holst

autor

J. Andrew McCammon

Bibliografia

• [1] L. Albou, B. Schwarz, O. Poch, J. Wurtz, and D. Moras. Defining and characterizing protein surface using alphashapes. 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 macromolecularstructures 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. Technicalreport, 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. Technicalreport, TICAM Technical Report, 1999.
• [6] C. L. Bajaj, V. Pascucci, A. Shamir, R. J. Holt, and A. N. Netravali. Dynamic maintenance and visualization ofmolecular surfaces. Discrete Applied Mathematics, 127(1):23–51, 2003.[Crossref]
• [7] C. L. Bajaj and V. Siddavanahalli. Fast error-bounded surfaces and derivatives computation for volumetric particledata. 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 channelingin 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 Paralleland 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]
• [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. ComputerPhysics Communications, 184:1490–1496, 2013.[Crossref]
• [16] W. Geng and R. Krasny. A treecode-accelerated boundary integral Poisson-Boltzmann solver for electrostatics ofsolvated 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. MolecularBased Mathematical Biology, 1:109–123, 2013.
• [18] J. Giard and B. Macq. Molecular surface mesh generation by filtering electron density map. International Journalof 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 equationalgorithms 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 surfaceconstruction. Molecular Based Mathematical Biology, 1:1–25, 2013.
• [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.
• [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 volumedefinition 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 segmentedtetrahedral 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-AidedDesign, 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]
• [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 maintenanceduring 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 interactionsin biomolecular systems. Journal of Computational Physics, 226:1348–1366, 2007.[Crossref]
• [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 contouringalgorithms 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 hierarchicalspace 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 andmutant 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-stateSmoluchowksi 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. Journalof 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. Proceedingsof 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 extractionand rendering. Journal of Parallel and Distributed Computing, 67(5):592–603, 2007.[Crossref]
• [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 electrodiffusionequations. Molecular Based Mathematical Biology, 1:90–108, 2013.
• [48] Z. Yu, Michael J. Holst, Y. Cheng, and J. A. McCammon. Feature-preserving adaptive mesh generation for molecularshape 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-stateSmoluchowski 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 AppliedMechanics and Engineering, 194(48-49):5083–5106, 2005.[Crossref]
• [51] Y. Zhang and J. Qian. Resolving topology ambiguity for multiple-material domains. Computer Methods in AppliedMechanics 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. ComputerAided Geometric Design, 23(6):510–530, 2006.[Crossref][PubMed]
• [53] Q. Zheng, S. Yang, and G. Wei. Biomolecular surface construction by PDE transform. International Journal forNumerical Methods in Biomedical Engineering, 28(3):291–316, 2012.

Identyfikatory

DOI

10.2478/mlbmb-2013-0009