Internal:GPCD

Introduction

Protein Cavities

Cavities are structural features of proteins and they are often important for drug discovery and design. There are different kinds of cavities, including pockets, voids, tunnels, and channels. The types of cavities are listed in more detail in figure 1.

Figure 1: The basic types of protein cavities [1]

1. Void: A cavity that looks like internal "hole" in a protein with no connection to the surface.
2. Cleft: A pocket that looks like a small "dent" in the surface of a protein. Can also be found as part of a tunnel or channel.
3. Invagination: A pocket that looks like a "cove". It has a small opening on the surface of a protein and leads to a larger interior. Can also be found as part of a tunnel or after a cleft.
4. Tunnel: A pocket that has an opening on the surface of a protein and leads to somewhere in the interior. Has no opening on the other side.
5. Channel: A cavity that has an opening on one side of the surface of a protein and leads to another opening in another location on the surface of the protein.

Of course, the types of cavities listed in figure 1 are only the basic ones. Combinations of these are also possible as shown in figure 2.

Figure 2: Combination types of protein cavities [1]

Protein Cavity Detection Methods

There are several methods for detecting protein cavities. There are sphere based methods, grid based methods, grid-and-sphere based methods, surface based methods, grid-and-surface based methods, time-varying methods, GPU based methods, consensus based methods, and finally tessellation based methods. These algorithms are shown in more detail in figure 3. Tessellation based methods mainly rely on Voronoi tessellation. Some methods rely on weighted Voronoi tessellation because of its ability to more accurately represent the volume of atoms. The Voronoi tessellation in these methods is computed from a set of points representing the atomic centers of the underlying protein.

Figure 3: A hierarchy of protein cavity detection algorithms [1]

New Parallel Methods

1. PODM Tessellation Using Van der Waals Surface Image Input

The first method that could be used for detecting protein cavities in parallel involves using PODM to create a tessellation of an image representation of the Van der Waals surface of a protein. The Van der Waals surface is an accurate representation of the surface of a protein and represents each atom as a sphere of a radius corresponding to its Van der Waals radius. The steps for this method are outlined below:

1. Compute the Van der Waals surface: This polygonal surface can be computed using UCSF Chimera. However, because the implementation is sequential, this step can present a major bottleneck in the overall method. In order to speed the process up, a custom parallel implementation to generate this surface is necessary.
2. Generate image of the Van der Waals surface: Because PODM requires an image as input, the polygonal Van der Waals surface needs to be converted to an image. This is done by "filling" the polygonal surface with a constant value. The segmentation module of 3D Slicer can be used for doing this, but as before, this step can present a major bottleneck because the implementation is sequential. A custom parallel implementation is once again necessary.
3. Compute Delaunay tessellation using PODM: Once we have the image of the Van der Waals surface, we use PODM to compute the Delaunay tessellation in parallel. A low enough delta should be used to ensure that the surface is as accurately captured as possible.
4. Compute Voronoi tessellation using PODM: The next step is to compute the Voronoi tessellation as the dual of the Delaunay tessellation in parallel. The Voronoi tessellation is useful for quickly identifying tunnels using Dijkstra's algorithm.
5. Identify cavities in parallel: With the Delaunay and Voronoi tessellations computed, the cavities now need to identified in parallel. It is crucial that this step is done in parallel as no other method implements "proper" parallelization. This is by far the most challenging step.
6. Output detected cavities as tessellations: The last step is to output the detected cavities as a tessellated mesh. It is important to only include the identified cavities in this mesh by representing them as tetrahedra. This way, researchers can overlay the normal protein structure with the tessellations of the cavities and easily see where they are.

Figure 4: A tessellation based on the Van der Waals surface of the COVID-19 spike glycoprotein (6vxx)

Challenges

There are several challenges that need to be addressed if we are to have a good parallel solution for detecting protein cavities.

1. Expensive Pre-Processing

The parallel methods involving the Van der Waals surface, especially the one with the image input have expensive pre-processing. For large molecules, getting this surface can be slow because existing implementations are sequential and written in Python. We need to come up with a way quickly generate this surface and its image representation.

Figure 5: The Van der Waals surface of the COVID-19 spike glycoprotein (6vxx)

2. Massive Parallelism

The solution we will implement may need to support massive parallelism, ideally using MPI. The reason for this is that molecular dynamics simulations can potentially involve a massive number of atoms. If we consider the 200 million coronavirus model, then a simulation containing 5000 frames, would involve a total of 1 trillion atoms. If we are to detect the cavities in every frame in real-time, a massively parallel solution is necessary. There is no doubt about why 250,000 CPU cores were required for the COVID-19 simulation.

Figure 6: An animation produced by a molecular dynamics simulation

Figure 7: An animation produced by the COVID-19 molecular dynamics simulation

References

[1] Simões, T., Lopes, D., Dias, S., Fernandes, F., Pereira, J., Jorge, J., Bajaj, C., & Gomes, A. (2017). Geometric Detection Algorithms for Cavities on Protein Surfaces in Molecular Graphics: A Survey. Computer graphics forum : journal of the European Association for Computer Graphics, 36(8), 643–683. https://doi.org/10.1111/cgf.13158