A general and robust ray-casting-based algorithm for triangulating surfaces at the nanoscale

Abstract

We present a general, robust, and efficient ray-casting-based approach to triangulating complex manifold surfaces arising in the nano-bioscience field. This feature is inserted in a more extended framework that: i) builds the molecular surface of nanometric systems according to several existing definitions, ii) can import external meshes, iii) performs accurate surface area estimation, iv) performs volume estimation, cavity detection, and conditional volume filling, and v) can color the points of a grid according to their locations with respect to the given surface. We implemented our methods in the publicly available NanoShaper software suite (www.electrostaticszone.eu). Robustness is achieved using the CGAL library and an ad hoc ray-casting technique. Our approach can deal with any manifold surface (including nonmolecular ones). Those explicitly treated here are the Connolly-Richards (SES), the Skin, and the Gaussian surfaces. Test results indicate that it is robust to rotation, scale, and atom displacement. This last aspect is evidenced by cavity detection of the highly symmetric structure of fullerene, which fails when attempted by MSMS and has problems in EDTSurf. In terms of timings, NanoShaper builds the Skin surface three times faster than the single threaded version in Lindow et al. on a 100,000 atoms protein and triangulates it at least ten times more rapidly than the Kruithof algorithm. NanoShaper was integrated with the DelPhi Poisson-Boltzmann equation solver. Its SES grid coloring outperformed the DelPhi counterpart. To test the viability of our method on large systems, we chose one of the biggest molecular structures in the Protein Data Bank, namely the 1VSZ entry, which corresponds to the human adenovirus (180,000 atoms after Hydrogen addition). We were able to triangulate the corresponding SES and Skin surfaces (6.2 and 7.0 million triangles, respectively, at a scale of 2 grids per Å) on a middle-range workstation.

Figure 1. Surfacing Steps.

On the left are the steps involved in the surfacing pipeline. On the right are the corresponding outcomes. 1) The surface is computed or externally loaded, 2) the surface is ray-cast, 3) cavities are detected and possibly removed, 4) the surface is triangulated.

Figure 2. Ray-casting procedure.

Rays are cast from each coordinate plane. In this 2D sketch, a coordinate plane is represented by a black line. For rays, orange segments correspond to the internal region. In black is the triangulation deduced from ray-surface intersections.

Figure 3. Ray casting on the surface.

In (1), rays are cast along the centers of the grid cubes to get the inside/outside information. Then (2), Edge Rays are cast and analytical intersections with the surface are calculated, inferring the inside/outside status of the vertices of each cube. Finally (3), the triangulation is performed employing the Marching Cubes triangulation maps.

Figure 4. Cavity detection.

Cavity detection for NanoShaper-built Gaussian, Skin, and SES.

Figure 5. Area estimation: surface definition comparison.

FAAH protein surface area estimates in case of Skin (), Gaussian , and SES (probe radius Å), with changing grid resolution and enabling cavity removal.

Figure 6. Volume estimation for the FAAH protein.

Estimated volume of the FAAH protein at varying grid resolutions and different molecular surface definitions. The upper panel represents a detailed comparison of the SES. Results show that NanoShaper SES after cavity removal is approximately equal to the main component generated by MSMS. In the lower panel for the Skin, we used a value of s = , for the Gaussian a value of B = , and for the SES a probe radius of Å.

Figure 7. Skin surface: performance.

Execution times and memory usage are reported in the upper and lower panels, respectively. The scale for each molecule was set accordingly to that assigned by EDTSurf .

Figure 8. Skin surface: mesh quality.

Comparison of the mesh of the Skin surface obtained by our algorithm (up) and CGAL (down) with a small detail highlighted.

Figure 9. SES: execution times.

Performance comparison of the total time needed to build, get cavities, and triangulate the SES for NanoShaper, EDTSurf, and MSMS. Detailed times for NanoShaper are in the lower panel.

Figure 10. SES: memory requirements.

Comparison of the peak memory needed to build and triangulate the SES for NanoShaper, EDTSurf, and MSMS.

Figure 11. SES: area and volume estimation.

Area and volume estimation of the Calmodulin SES made by NanoShaper, EDTSurf, and MSMS at different scale/vertex densities.

Figure 12. SES: MSMS false positive identification of a cavity.

In this figure, a schematic illustration of how the MSMS algorithm can confuse an accessible region with an internal cavity during the SES construction. The probe can roll both inside and outside. In MSMS, this task is performed in two separate steps. If self-intersections occur at the entrance(s) of a given region, they may lead to the depicted situation and to the incorrect detection of a cavity.

Figure 13. Area estimation: methods comparison.

Here, area estimation methods are compared upon rotation of the 1HF0 and 1QA7 molecules.

Figure 14. Pre-processing for PDE solution: execution times and accuracy assessment.

Comparison of execution times for grid coloring and boundary grid points projection for NanoShaper surfaces and DelPhi. A set of increasingly bigger molecules is used as benchmark. In the lower panel, percentage energy difference of different MS definitions and methods as compared to the DelPhi solver.