Neighbor-list reduction: Optimization for computation of molecular van der Waals and solvent-accessible surface areas

A general, fast, and exact optimization, called neighbor-list reduction (NLR), is presented, which can be used to accelerate the computation of hard-sphere molecular surface areas. NLR allows selected neighbors of a central atom to be removed from the computation in a preprocessing step, thus allowing the calculation of the atom's surface area to proceed with a shorter list of neighbors. The atoms removed are those having intersections with the central atom falling entirely within unions of other atoms' intersections with the central atom. We describe explicit methods for two levels of neighbor-list reduction: 3NLR considers three hard spheres at a time—the central atom, the candidate for removal, and one other neighbor; whereas 4NLR considers two other neighbors. We demonstrate the correctness and efficiency of this optimization by means of a modified version of the NACCESS program, which computes atomic and molecular surface areas numerically. As test cases we used compounds of different size and class, with and without explicit hydrogens. When van der Waals surface (vdWSA) is computed, the NLR methods reduce the length of the neighbor list by as much as 41%; when solvent-accessible surface area (SASA) is computed, the reduction is as great as 74%. The overall speed improvement due to these reductions is a factor of only about 1.2 for vdWSA, but is about 2.0 for the computation of SASA, in the context of this particular program. All 39,554 calculated atomic surface areas (vdWSA and SASA) were found to be identical to within 0.001 Å2 to those obtained without NLR. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 797–808, 1998