System that rapidly generates a solvent-excluded surface

System that generates the solvent-excluded surface (SES) of a molecule using a parallel algorithm that may execute on a GPU. Parallel execution allows a SES to be created in seconds even for a large protein, or to be recreated rapidly when exploring modifications to molecular structure. The algorithm calculates a spatial field that represents a signed distance between an atom-facing surface of a probe and each point in 3D grid. Spatial field calculations for different grid points may be performed in parallel. The SES is then obtained as the zero isosurface of the spatial field, using for example marching cubes. Atoms and probes may be placed into spatial buckets and indexed by bucket to improve efficiency by limiting calculations to atoms and probes in the proximity of a point.

BACKGROUND OF THE INVENTION

Field of the Invention

One or more embodiments of the invention are related to the field of scientific visualization of molecules. More particularly, but not by way of limitation, one or more embodiments of the invention enable a system that rapidly generates a solvent-excluded surface.

Description of the Related Art

A solvent-excluded surface, also known as a Connolly surface, is a useful tool for molecular visualization, modeling, and simulation. This surface models the volume occupied by a molecule in a solvent if solvent molecules approach as closely as possible to the atoms of the molecule. The solvent is often taken to be water.

Methods are known for calculating a solvent-excluded surface from a molecular model, including the original method described in Connolly, Michael L., “Solvent-accessible surfaces of proteins and nucleic acids,”Science221 4612 (1983): 709-13. A drawback of the known methods for calculating solvent-accessible surfaces is that they can be very slow for very large molecules, such as proteins with tens or hundreds of thousands of atoms. The known methods are primarily sequential algorithms that do not take advantage of modern highly parallel processors such as GPUs. While surfaces can be computed offline for some known molecules, researchers often want to model modifications to molecular structure and then see the effects of these modifications on the solvent-excluded surface. With current methods for calculating solvent-excluded surfaces, a long delay may be introduced between making a modification and updating the solvent-excluded surface.

For at least the limitations described above there is a need for a system that rapidly generates a solvent-excluded surface.

BRIEF SUMMARY OF THE INVENTION

One or more embodiments described in the specification are related to a system that rapidly generates a solvent-excluded surface. The solvent-excluded surface may be calculated using a highly parallelizable algorithm that may execute largely on a GPU; parallel execution enables calculation or recalculation of the surface to be performed rapidly in comparison with sequential methods.

One or more embodiments may incorporate or use computer hardware including a processor with an attached memory and display. The processor may be configured to obtain a 3D model of a molecule, obtain a probe radius (which represents a solvent), and calculate the solvent-excluded surface of the molecule. The 3D model of the molecule may contain descriptions of the atoms of the molecule, including the location of their centers and their radii. Calculation of the solvent-excluded surface may generate a collection of probes around each atom. For each atom, these probes may be centered at vertices on a sphere around the atom's center with a radius equal to the atom radius plus the probe radius. Each probe may be represented at a sphere with a radius equal to the probe radius. The system may test each probe for whether it intersects any atom at more than one point, and if so that probe may be removed from the final probe list. The system may then calculate the value of a spatial field at points of a 3D grid that covers a volume (such as a bounding box) that contains the atoms and the final probes. This value may represent a minimum signed distance from each grid point to the atom-facing portion of a probe surface. The sign of this value may be different on the atom-facing side, which includes atom centers, and the probe-facing side, which include probe centers. The solvent-excluded surface may then be calculated as the zero isosurface of this spatial field. In one or more embodiments the processor may then display the solvent-excluded surface on the display.

The vertices used for generation of probes may be for example vertices of an icosphere centered at an atom center.

In one or more embodiments the zero isosurface of the spatial field may be calculated using a marching cubes algorithm.

In one or more embodiments the processor may groups atom into spatial buckets; this may improve efficiency of the calculations. To test whether a probe intersects an atom in more than one point, the system may identify the spatial bucket containing the probe center, identify a group of spatial buckets equal to or near this bucket, retrieve the atoms in that group of spatial buckets, and test for intersection of the probe with those atoms.

Calculating the value of the spatial field at a grid point may for example incorporate three steps in one or more embodiments. In the first step, the system may calculate a first value that is the minimum of the distance between the grid point and an atom center less the atom radius less the probe radius. This first value is an indication of whether a grid point is on the atom-facing side of a probe or on the side of a probe facing away from an atom. In the second step, the system may calculate a second value that is the minimum distance between the grid point and the centers of the final probes, less the probe radius. This second value is an indication of whether a grid point is inside a probe or is outside all probes. In the third step, the spatial field value may be set based on the sign of the first value: if the first value is negative or zero, the spatial field value may be set to the second value; if the first value is positive, the spatial field value may be set to the negative of the sum of the second value and twice the probe radius.

In one or more embodiments, the processor may group both atoms and the final probes into spatial buckets. The calculation of the first value may identify spatial buckets equal to or near the bucket containing a grid point, and may minimize the first value only over atoms in those spatial buckets. Similarly, the calculation of the second value minimize the second value only over probes in those spatial buckets.

In one or more embodiments, the processor may contain or may be coupled to a parallel processing unit, such as a GPU for example, that can execute computational tasks in parallel. Several of the calculations described above may be parallelized on this parallel processing unit. For example, the test of whether a probe intersects any atoms may be performed in parallel over the set of probes, with a computational task executed for each probe in parallel with corresponding computational tasks for one or more other probes. As another example, the calculation of the spatial field value for each grid point may be performed in parallel over the set of grid points, with a computational task executed for each grid point in parallel with corresponding computational tasks for one or more other grid points.

One or more embodiments that include a parallel processing unit may also perform parallel processing to generate the zero isosurface of the spatial field. The volume containing the molecule and the probes may be partitioned into cells, and a computational task may be generated for each cell to determine whether a portion of the zero isosurface passes through the cell, and if so to determine this portion. The computational task for a cell may be executed in parallel with corresponding computational tasks for one or more other cells.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1illustrates an overview of the inputs and output of one or more embodiments of the system. The system may obtain or create a molecular model101. This model may for example describe the positions and sizes of the atoms in the molecule. The “molecule” in some situations may be multiple molecules that are considered as a unit for purposes of calculating a surface. While the molecule shown inFIG. 1is extremely small for ease of illustration, in some applications embodiments of the invention may receive molecular models containing tens or hundreds of thousands of atoms, for example for large proteins. In addition to the molecular model101, a model102of the solvent may also be received by or generated by the system. In many applications the solvent102may be water; however, one or more embodiments of the system may be used with any type of solvent. For surface calculations, it is common practice to simplify the solvent model to a single sphere with a solvent radius103. This radius may be for example the van der Walls radius of the solvent.

Inputs101and103may be processed by system105to generate a solvent-excluded surface104of the molecule101with solvent102. One or more embodiments may be used to generate other molecular surfaces using techniques similar to those described below. For example, without limitation, one or more embodiments may generate a solvent-accessible surface. One or more embodiments may also generate metrics associated with a surface, such as for example surface area.

FIG. 2shows illustrative data201associated with molecular model101. Each atom in model101may be described by a position202in 3D space, and by a radius203of the atom, which may be for example the atom's van der Walls radius. The position202may be measured with respect to a reference frame for the 3D model.

FIG. 3illustrates high-level steps that may be performed by one or more embodiments of the system to transform inputs101and103into surface104. One or more embodiments may perform these steps in different orders or may omit certain steps, add other steps, or combine certain steps. The dependencies shown among steps inFIG. 3are also illustrative and may be modified in one or more embodiments.

Any or all of the steps shown inFIG. 3may be parallelized, to execute fully or partially on a GPU for example. This parallelization may enable the system to generate a solvent-excluded surface rapidly, even for very large molecules. Rapid generation of the solvent-excluded surface may be particularly valuable in applications where a user is modifying a molecular model (for example during drug development), since the updated surface associated with a modified molecule may be calculated quickly. The parallelizability of significant portions of the processing performed by the system represents a benefit of the invention compared to existing sequential implementations of solvent-excluded surface calculations.

Each of the steps301through306will now be described briefly, with detailed descriptions provided below with respect to subsequent figures. Step301places atoms into spatial buckets, which increases processing efficiency by limiting calculations to atoms in the vicinity of a point. Parts of this step may be parallelized across atoms. Step302generates possible probes around each atom, which may also be performed in parallel across atoms. Step303checks the possible probes generated in step302for whether they intersect any atoms; if so, they are excluded since they do not contribute to the solvent-excluded surface. Step303may be performed in parallel across probes, and it may use the spatial buckets for atoms developed in step301. Step304puts probes in spatial buckets, analogously to the placing of atoms in buckets in step301. Step305generates a spatial field at grid points across the molecular model. Values of the spatial field may be calculated in parallel across grid points. The spatial field represents roughly a signed distance to the nearest inner probe surface. Finally, step306generates the solvent-excluded surface from the spatial field by locating the isosurface for the zero value of the field. Step306may be parallelized over cells (which have corners at grid points, for example).

The steps301through306are executed on one or more processors associated with one or more computers.FIG. 4shows an architecture of illustrative computer hardware that may be used by or incorporated into one or more embodiments of the invention. The components shown inFIG. 4are illustrative; one or more embodiments may use computers with other components, fewer components, or additional components. One or more embodiments may use or incorporate multiple computers, for example in a distributed system, to further accelerate processing; the parallelizability of the steps ofFIG. 3may also facilitate use of distributed processing.

FIG. 4shows an embodiment of exemplary computer400that may be utilized in, by, or as any component in the system. In one or more embodiments, computer400may be a network of computers, each of which may have any or all of the components shown inFIG. 4. In one or more embodiments, computer or computers400may also be utilized to implement any function in the system, i.e., any step or act or function that executes in any computer or server or engine in the system. Computer400may include processor CPU407that executes software instructions specifically tailored to the respective functions of embodiments of the invention. The software instructions, otherwise known as computer program instructions, may reside within memory406. Computer400may include processor GPU405, which may execute graphics instructions or other instructions for highly parallel operations, for example. GPU program instructions may also reside within memory406. Computer400may include display interface408, which may drive display unit or units410of any computer in the system as desired. Some computers400may or may not utilize a display. Computer400may include communication interface424, which may include wireless or wired communications hardware protocol chips. In one or more embodiments of the invention communication interface424may include telephonic and/or data communications hardware. In one or more embodiments communication interface424may include a Wi-Fi™ and/or BLUETOOTH™ wireless communications interface. Any wireless network protocol or type may be utilized in embodiments of the invention. CPU407, GPU405, memory406, display interface408, communication interface424, human interface devices430, secondary memory412, such as hard disk414, removable storage416, secondary memory interface420and removable storage units418and422may communicate with one another over communication infrastructure402, which is commonly known as a “bus”. Communications interface424may communicate over any wired or wireless medium that allows for communication with other wired or wireless devices over network440. Network440may communicate with Internet460and/or database or databases450. Database450may be utilized to implement any database described herein.

FIG. 5shows how processing may be partitioned between CPU407and GPU405in one or more embodiments of the system. CPU407may perform steps501to initialize data and code for parallel execution on GPU405. GPU405may perform steps502to execute steps301to306ofFIG. 3. The multiple cores of the GPU may act in parallel on the various data units such as atoms, probes, grid points, or cells. For example, if a calculation needs to be performed for all atoms, and if this calculation has no interdependencies among atoms, then each core of the GPU may perform a calculation for one atom in parallel with the other cores performing this calculation for other atoms. Groups of atoms may be pipelined through the multiple cores if there are not enough cores to work on all atoms at once.

GPU405may then perform step503to render a final solvent-excluded surface. The final surface may be transmitted to display unit410for display step504. The CPU and GPU may communicate throughout execution of steps301to306. In one or more embodiments the display step504may be performed at a later time, or on another computer system; for example, one system may calculate the solvent-excluded surface and store it for later use or transmit it over a network to a client computer.

FIGS. 6 through 17describe the steps301through306in more detail. In these figures, molecules, atoms, probes, spatial fields, are shown in two dimensions for ease of illustration, and “surfaces” are shown as two-dimensional curves. In application, molecular models and surfaces are typically three dimensional. The processes and algorithms described and illustrated in 2D may be implemented immediately in 3D with no fundamental changes (other than adding an additional dimension to the various spatial data structures). In general, in the descriptions below we refer to “spheres” and “surfaces” because these will be the three-dimensional objects used in practice in embodiments of the invention; however, these “spheres” and “surfaces” will be illustrated in the Figures as circles and curves in two dimensions.

FIG. 6illustrates step601, placing atoms into spatial buckets. Some of the steps described below involve calculation of distances between a point and the “closest” atom to the point. A naïve implementation involves calculation of distances to each atom, and selecting the smallest result. For large molecules, this approach may involve hundreds of thousands of distance calculations for each point. To reduce the number of calculations, one or more embodiments develop a spatial index so that the atoms nearest a point can be identified rapidly. Atoms601are overlaid with a grid of spatial buckets602. Buckets may be of any desired size, and the grid may contain any number of buckets. Each atom may be mapped to the bucket containing the atom's center, resulting in list603. Calculation of which bucket each atom is in is straightforward; for example, if the area spanned by bucket grid602is [0,1]2, then an atom with center at (x, y) is in the bucket with index 1+int(5x)+5*int(5y). This calculation may be done in parallel for each atom on a GPU. List603may then be sorted in operation604by bucket index, resulting in sorted list605. The sort may be performed for example on a GPU as a radix sort, or using any other sort algorithm. Finally, an inversion operation606may generate an index607that maps bucket indices into the sorted atom list605, so that the atoms in a bucket may be quickly retrieved.

FIG. 7illustrates how the bucket-to-atom mapping may be used in one or more embodiments. A calculation may involve for example distances between point701and nearby atoms. The bucket index of the point may be determined (here it is 7), and the buckets in the neighborhood of the point's bucket may be identified. For example, the neighborhood to be considered may be all buckets in the 3×3 subgrid702centered at the point's bucket. This 3×3 neighborhood is illustrative; one or more embodiments may search for atoms in any neighborhood around a point's bucket. The bucket indices of buckets in the subgrid702may be calculated directly from the index of the point's bucket. The atoms in these buckets may then be obtained from index607and sorted atom list605. For example, atom703is determined to be in this neighborhood because it is in bucket11.

The process of locating neighboring buckets is similar in three dimensions. For example, buckets in the neighborhood of point710may be the 3×3×3 subgrid711, which includes bucket712but excludes bucket713. The 3×3×3 neighborhood is illustrative; one or more embodiments may use any bucket neighborhood size, including for example a 1×1×1 neighborhood (which includes only the bucket containing the point) or a larger 5×5×5 neighborhood.

FIGS. 8A through 8Cshow a conceptual framework for defining the solvent-excluded surface around a molecule. For ease of illustration in these and subsequent figures, we use a simple two-atom molecule consisting of atoms801and802, shown inFIG. 8A. The solvent-excluded surface is described by placing copies of a solvent803, modeled as a sphere (shown as a circle in 2D) against the atoms801and802. These copies are called “probes.” This process is illustrated inFIG. 8B, which shows a “cloud” of probes810surrounding the molecule. Conceptually probe spheres may be in any position tangent to any of the atoms of the molecule, resulting in an infinite cloud of probes.FIG. 8Bshows a sampling of these probe spheres at selected locations. The solvent-excluded surface is defined as the envelope of the inner surfaces of the probes. This surface820is shown inFIG. 8C. In the simple two atom molecule, portions of the solvent-excluded surface coincide with the outer surface of the atoms, but there is a gap811between the atoms that a probe cannot penetrate.

One or more embodiments of the system effectively recreate the process illustrated inFIGS. 8A through 8Cby generating probes around atoms of the molecule and calculating an envelope of their inner surfaces. Instead of an infinite cloud of probes, embodiments generate a sampling of probe spheres at discrete locations around each atom.FIG. 9Ashows illustrative probes generated around atoms801and802. Every probe must be tangent to at least one atom in a molecule. For example, probe903is tangent to atom801, and probe905is tangent to atom802. A probe is tangent to an atom when the center of the probe lies on a sphere (shown as a circle in 2D) surrounding the atom center with a radius equal to the atom radius plus the probe radius. For example, the center904of probe903lies on sphere901, and the center906of probe905lies on sphere902. This observation leads to the technique illustrated inFIGS. 9B and 9Cfor generating possible probes: an “extended atom sphere” is generated around each atom, with a radius equal to the atom radius plus the probe radius, and probes are generated with centers on these extended atom spheres.

FIG. 9Bshows an illustrative method of generating probe centers: a regular polygon is inscribed in the extended atom sphere around each atom, and probe centers are generated on the vertices of these polygons. In three dimensions, the regular polygons may be for example icospheres, or any type of polyhedra. One or more embodiments may use any method for sampling points on extended spheres around atoms to generate probe centers. InFIG. 9B, eight points per atom are generated by inscribing octagon911in sphere901, and octagon912in sphere902. Illustrative probe centers913and914are generated at vertices of these octagons. The use of polygons with8vertices is illustrative; one or more embodiments may use polyhedra (illustrated with polygons in 2D) with any number of vertices. A tradeoff in the selection of how many vertices to use around each atom is generating a smoother solvent-excluded surface with more vertices at the expense of more computation.

FIG. 9Cshows the result of step302to generate the initial probes around each atom. In this illustrative example, shown in 2D, 8 probes are generated around each atom, for a total of 16 probes. For example, probe923is generated with a center at vertex913of octagon911, and probe924is generated with a center at vertex914of octagon912.

The next step303in one or more embodiments of the invention is to eliminate probes that intersect an atom at more than a single tangent point.FIG. 10Aillustrates the probes fromFIG. 9Coverlaid onto atoms801and802. Four of these probes intersect with atoms. For example, probe1001intersects with atom801, and probe1002intersects with atom802(where “intersect” means intersecting at more than a single tangent point). These probes and two additional probes cannot represent solvent molecules on the surface of the molecule because they would imply that the solvent overlaps with an atom. Therefore, these intersecting probes are removed from the list of probes, leaving the final probes1010shown inFIG. 10B, such as probes1011and1012.

Determining whether a probe and an atom intersect is a simple calculation, illustrated inFIG. 10C. The distance1021between the center of an atom802and the center of a probe102is compared to the sum of the atom radius1022and the probe radius1023. If the distance1021is smaller than the sum of the radii1022and1023, then the two spheres intersect at multiple points. This calculation may be performed for each probe and atom combination to check for intersections. However, the number of tests may be reduced by using the atom spatial buckets to locate atoms near each probe, and to check for probe intersections only with these atoms. The retrieval of atoms to check for each probe and the calculation of distances to test for intersection may be parallelized across probes, for example on a GPU, since the operations are independent across probes.

After the final list of probes1010is generated, by removing probes that overlap with atoms, the probes may be placed into spatial buckets in operation304, which is illustrated inFIG. 11. This operation is analogous to the step301to place atoms into spatial buckets, which is shown inFIG. 6. For ease of illustration the same grid of buckets602is shown inFIG. 11for the probes; one or more embodiments may use either the same or different buckets for atoms and for probes. The probes1010are mapped to buckets and the list1101is sorted by bucket. An index1102may be generated to support fast retrieval of the probes in each bucket. These operations may be parallelized on a GPU across probes. For example, list1101may be sorted by bucket on a GPU using a radix sort.

The next step in construction of the surface is to define and calculate a spatial field from which the desired surface can be obtained. The solvent-excluded surface will be the isosurface of the spatial field at the zero value. Conceptually the spatial field will measure how far a point is from the desired solvent-excluded surface, which is the atom-facing “inner” side of the probes' surfaces. It will be defined as a signed distance from the inner side of the probe surface, with the sign set to positive on the “atom side” and negative on the “probe side.”

FIGS. 12A and 12Billustrate a preliminary step in constructing an appropriate spatial field. For ease of illustration, we show only a single atom801and two probes1201and1202. The desired portion of the solvent-excluded surface is the atom-facing section1211of the surface of probe1201and the atom-facing section1212of the surface of probe1202. These surface portions1211and1212partition the space into an “outside” region1203and an “inside” region1204. The spatial field should have a positive value in the outside region, a negative value in the inside region, and a zero value on the surfaces122and1212. A preliminary function that has these features is function1230, which measures the minimum distance between a point and a probe center, less the probe radius. This function is positive for a point that is outside all probes, and is negative for a point that is inside one or more probes.FIG. 12Ashows illustrative points in the space;FIG. 12Bshows the value of function1230at these points on number line1231, with positive values shown in red, negative values shown in blue, and zero values shown in white. The center1221of atom801has a positive value, because it is outside all probes. The center of any atom will be outside all probes, because the distance to a probe center is at least the atom radius plus the probe radius; hence the function1230will be positive at each atom center. The point1222has a positive value because it is outside both probes1201and1202. Point1223on the surface1212has a zero value, as desired. Point1224has a negative value because it is inside probe1202. The centers1225and1226of probes1201and1202have negative values. Any probe center will have a negative value because the value of function1230at a probe center is the negative of the probe radius.

FIG. 13shows a “heat map”1310that illustrates the spatial field of function1230for the example molecule consisting of atoms801and802. Positive values of the spatial field are shaded red, negative values are shaded blue, and zero values are shaded white. This heat map shows that the desired solvent-excluded surface is a zero isosurface1301. For the function1230, there is a second zero isosurface1302on the non-atom facing portion of the probe surfaces. One or more embodiments may process the spatial field1310to select only the inner isosurface1301as the solvent-excluded surface. The outer surface1302may also be generated by one or more embodiments as it may be useful for certain analyses or molecular visualizations.

FIGS. 14A, 14B, and 15illustrate a method that may be used in one or more embodiments to adjust the function1230so that only the inner zero isosurface1301is present; this may simplify generation of the solvent-excluded surface in certain applications.FIG. 14Aillustrates a heat map1310afor function1230around a single atom801.FIG. 14Bshows a plot1420of the function1230along a ray1401from the center1401of atom801through the center1403of probe1202, as a function of the distance r from the atom center1401. At point1401, plot1420has a positive value as expected. The function value declines to zero at point1402and to a negative value at the center1403of the probe. After point1403, the plot1403begins to increase and crosses zero at point1404, on the other non-atom-facing side of the probe surface. To modify the function1230to eliminate the outer zero isosurface, the function may be modified after point1403to continue its negative slope instead of turning upwards. This corner in the function occurs in general for points outside the “extended atom” sphere1410with radius equal to the atom radius plus the probe radius. As the plot1420indicates, inside the sphere1410the function value is ƒ(r)=r1−r, where r1is the radius of atom801. Outside the sphere1410the function value is ƒ(r)=r−r1−2rp, where rpis the radius of the probe. Therefore, the function may be modified with formula1422by adding 2rpto its value and inverting it in the region outside extended atom sphere1410. This generates segment1421of the function that avoids the corner at point1403.

FIG. 15shows the result of this modification in heat map1510. The formulas1500illustrate the calculations that generate a function1502that is used for the spatial field. This function is equal to the previously described function1230for points that are inside any “extended atom sphere.” Outside these extended atom spheres, the function is adjusted as described with respect toFIG. 14B. Function1501determines whether a point is inside or outside an extended atom sphere. The adjusted function1502has a single zero isosurface1301, as desired, which is the solvent-excluded surface.

FIG. 16illustrates a method for generating the spatial field1510that may be used in one or more embodiments. A bounding volume (such as a box for example) may be calculated around the molecule and the probes, and a grid of points may be overlaid onto this bounding volume. The function may be evaluated at the points of the grid to provide an approximation of the spatial field.FIG. 16shows a small portion1601of a grid of points in a region surrounding the atoms and probes of the running example molecule. Grid points such as point1611are obtained or generated from the grid. To optimize the calculation of values1230and1501, which involve minimizing distances over probes and atoms, the neighboring buckets1612of grid point1611may be used along with the sorted atom and probe lists and related indices605,607,1101, and1102, to locate the atoms and probes1613in the vicinity of the grid point. These atoms and probes1613may then be used along with grid point1611to perform the spatial field calculations1500. These calculations and steps may be parallelized over grid points since they are no dependencies among different grid points.

The final step306of generating the solvent-excluded surface as the zero isosurface of the spatial field is illustrated inFIG. 17. The bounding volume surrounding the molecule and the probes is partitioned into cells with corners at grid points. The cells may be for example cubical or tetrahedral, or in general may be any polyhedral shape. For each cell, the spatial field values at the corner grid points are used to determine whether the zero isosurface of the field passes through the cell, and if so where it intersects the cell. One or more embodiments may use for example a marching cubes algorithm or a variant thereof to locate the zero isosurface from the corner values of cubical cells. This process is illustrated inFIG. 17with an array of cells overlaid onto spatial field map1510. For cell1701, the values of grid points at the four corners of the cell are all negative; hence the zero isosurface does not pass through this cell. For cell1701, the spatial field value at corners1703aand1703bis positive, while the value at corners1703cand1703dis negative; hence the system determines that a portion1704of the zero isosurface passes through the cell. Determination of whether and where a zero isosurface passes through a cell may be parallelized over cells, for example on a GPU. The portions of the zero isosurface in cells such as1704are then combined to form the final solvent-excluded surface1710. This surface may then be displayed as part of a molecular visualization system or molecular design system, or stored for future use.

Because of the parallelization possible with the steps described above, and because of other efficiencies due to spatial indexing of atoms and probes, embodiments of the invention may generate a solvent-excluded surface much more rapidly than many existing systems. This performance improvement is illustrated inFIG. 18. This figure shows benchmarks of the time to generate a solvent-excluded surface for molecules of various sizes (with models obtained from the Protein Data Bank). The surfaces for these molecules were generated using an embodiment of the invention, and using two common molecular visualization systems: Pymol™ and ChimeraX™. The plot is a log-log plot, so spacing between horizontal gridlines represents an order of magnitude (10×) difference in performance. Line1801shows performance of the embodiment of the invention; line1802shows performance of ChimeraX; and line1803shows performance of Pymol. The rightmost point on each line is performance on the largest molecule benchmarked1804, which has 307,033 atoms. For this large molecule, the embodiment of the invention took 0.5 seconds to generate a solvent-excluded surface; Chimera took 35.3 seconds−a 70× difference, and Pymol took 161.5 seconds−a 320× difference. These benchmarks illustrate that embodiments of the invention may make a dramatic improvement in the time to generate a solvent-excluded surface. With embodiments of the invention, rapidly generating a solvent-excluded surface becomes practical even for large molecules, which may facilitate interactive exploration of molecules and interactive modification of molecular structures.