Abstract

Faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules is presented. The ASA is computed by finding the exposed surface areas of the spheres obtained by increasing the van der Waals' radii of the atoms with the van der Waals' radius of the solvent, and it can be used for energy calculations and protein folding prediction. Using domain specific knowledge, it can be shown that the number of sphere intersections is only O(n), where n is the number of atoms in the protein molecule. For computing sphere intersections, two algorithms are presented: hash-based algorithms that run in O(n) expected sequential time and O(n/p) expected parallel time and sort-based algorithms that run in worst-case O(n log(n)) sequential time and O(n log(n)/p)parallel time. These are significant improvements over previously known algorithms which take O(n^2) time sequentially and O(n^2/p) time in parallel. A Monte Carlo algorithm is presented for computing the solvent accessible surface area. The basic idea is to generate points uniformly at random on the surface of spheres obtained by increasing the van der Waals' radii of the atoms with the van der Waals' radius of the solvent molecule and to test the points for accessibility. Error bounds as a function of the sample size is also provided. Experimental verification of the algorithms was carried out using an IBM SP-2.