Efficient Parallel Algorithms for Solvent Accessible Surface Area of Proteins Export

@article{citeulike:3992115, abstract = {We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. 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. Using domain specific knowledge, we show 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, we present hash-based algorithms that run in O(n) expected sequential time and O\left({n\over p}\right) expected parallel time and sort-based algorithms that run in worst-case O\left(n\log n\right) sequential time and O\left({n\log n\over p}\right) parallel time. These are significant improvements over previously known algorithms which take O\left(n^2\right) time sequentially and O\left(\frac{n^2}{p}\right) time in parallel. We present a Monte Carlo algorithm 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. We also provide error bounds as a function of the sample size. Experimental verification of the algorithms is carried out using an IBM SP-2.}, address = {Piscataway, NJ, USA}, author = {Futamura, Natsuhiki and Aluru, Srinivas and Ranjan, Desh and Hariharan, Bhanu}, citeulike-article-id = {3992115}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=570543.570545}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/TPDS.2002.1011399}, doi = {10.1109/TPDS.2002.1011399}, issn = {1045-9219}, journal = {IEEE Trans. Parallel Distrib. Syst.}, keywords = {methods}, number = {6}, pages = {544--555}, posted-at = {2009-02-23 11:57:25}, priority = {2}, publisher = {IEEE Press}, title = {Efficient Parallel Algorithms for Solvent Accessible Surface Area of Proteins}, url = {http://dx.doi.org/10.1109/TPDS.2002.1011399}, volume = {13}, year = {2002} }

TY - JOUR ID - citeulike:3992115 L3 - citeulike-article-id:3992115 N2 - We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. 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. Using domain specific knowledge, we show 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, we present hash-based algorithms that run in O(n) expected sequential time and O\left({n\over p}\right) expected parallel time and sort-based algorithms that run in worst-case O\left(n\log n\right) sequential time and O\left({n\log n\over p}\right) parallel time. These are significant improvements over previously known algorithms which take O\left(n^2\right) time sequentially and O\left(\frac{n^2}{p}\right) time in parallel. We present a Monte Carlo algorithm 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. We also provide error bounds as a function of the sample size. Experimental verification of the algorithms is carried out using an IBM SP-2. IS - 6 JF - IEEE Trans. Parallel Distrib. Syst. SN - 1045-9219 AD - Piscataway, NJ, USA EP - 555 TI - Efficient Parallel Algorithms for Solvent Accessible Surface Area of Proteins PB - IEEE Press VL - 13 SP - 544 KW - methods AU - Futamura, Natsuhiki AU - Aluru, Srinivas AU - Ranjan, Desh AU - Hariharan, Bhanu PY - 2002/// UR - http://dx.doi.org/10.1109/TPDS.2002.1011399 ER -