We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of pro-tein molecules. The ASA can be obtained by calculating the exposed surface area of the spheres obtained by in-creasing the van der Waals' radii of the atoms with the van der Waals' radius of the solvent. Using domain spe-cific knowledge, we show that the number of sphere inter-sections is O(n) and present algorithms to compute the same in O(n log n) sequential time and O() par-allel time, where n is the number of atoms and p is the number of processors. We also present a geuristic based on space-filling curves to improve performance in practice. These are significant improvemtnts over previously known algorithms which take time sequentially and time in parallel. While existing parallel algorithms achieve their run-time by dynamic load balancing, our algorithms are faster and do not need load balancing.
展开▼
