Efficient algorithms for protein solvent accessible surface area

N. Futamura, S. Aluru, D. Ranjan, K. Mehrotra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. The ASA can be obtained by calculating the exposed surface area of the spheres obtained by increasing the van der Waals' radii of the atoms with the van der Waals' radius of the solvent. Using domain specific knowledge, we show that the number of sphere intersections is O(n) and present algorithms to compute the same in O(nlogn) sequential time and O(nlogn/p) parallel time, where n is the number of atoms and p is the number of processors. We also present a heuristic based on space-filling curves to improve performance in practice. These are significant improvements over previously known algorithms which take Ω(n2) time sequentially and Ω(n2/p) 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.

Original languageEnglish (US)
Title of host publicationProceedings - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages586-592
Number of pages7
ISBN (Electronic)0769505902, 9780769505909
DOIs
StatePublished - Jan 1 2000
Event4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000 - Beijing, China
Duration: May 14 2000May 17 2000

Publication series

NameProceedings - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000
Volume2

Other

Other4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000
CountryChina
CityBeijing
Period5/14/005/17/00

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Efficient algorithms for protein solvent accessible surface area'. Together they form a unique fingerprint.

  • Cite this

    Futamura, N., Aluru, S., Ranjan, D., & Mehrotra, K. (2000). Efficient algorithms for protein solvent accessible surface area. In Proceedings - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000 (pp. 586-592). [843502] (Proceedings - 4th International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, HPC-Asia 2000; Vol. 2). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPC.2000.843502