Document Open Access Logo

Parallel Computation of Alpha Complexes for Biomolecules

Authors Talha Bin Masood , Tathagata Ray, Vijay Natarajan

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.17.pdf
  • Filesize: 1.88 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
  • Computing methodologies → Shape modeling
  • Applied computing → Molecular structural biology
Keywords
  • Delaunay triangulation
  • parallel algorithms
  • biomolecules
  • GPU

Metrics

Abstract

The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are optimized for biomolecules.

Cite As Get BibTex

Talha Bin Masood, Tathagata Ray, and Vijay Natarajan. Parallel Computation of Alpha Complexes for Biomolecules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.17

Author Details

Talha Bin Masood
  • Scientific Visualization Group, Linköping University, Norrköping, Sweden
Tathagata Ray
  • BITS Pilani, Hyderabad Campus, Hyderabad, India
Vijay Natarajan
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

Funding

  • Natarajan, Vijay: This work is partially supported by a Swarnajayanti Fellowship from the Department of Science and Technology, India (DST/SJF/ETA-02/2015-16); a Mindtree Chair research grant; and the Robert Bosch Centre for Cyber Physical Systems, IISc.

Acknowledgements

Part of this work was done when the first author was at Indian Institute of Science, Bangalore. The authors would like to thank Sathish Vadhiyar and Nikhil Ranjanikar for helpful discussions and suggestions during the early phase of this work.

Supplementary Materials

References

  1. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. URL: https://doi.org/10.1142/8685.
  2. Ulrich Bauer and Herbert Edelsbrunner. The Morse theory of Čech and Delaunay filtrations. In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, page 484. ACM, 2014. URL: https://doi.org/10.1145/2582112.2582167.
  3. A Bondi. van der Waals volumes and radii. The Journal of Physical Chemistry, 68(3):441-451, 1964. Google Scholar
  4. Adrian Bowyer. Computing Dirichlet tessellations. Comput. J., 24(2):162-166, 1981. URL: https://doi.org/10.1093/comjnl/24.2.162.
  5. Thanh-Tung Cao, Ashwin Nanjappa, Mingcen Gao, and Tiow Seng Tan. A GPU accelerated algorithm for 3d Delaunay triangulation. In John Keyser and Pedro V. Sander, editors, Symposium on Interactive 3D Graphics and Games, I3D '14, San Francisco, CA, USA - March 14-16, 2014, pages 47-54. ACM, 2014. URL: https://doi.org/10.1145/2556700.2556710.
  6. Paolo Cignoni, Claudio Montani, and Roberto Scopigno. DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d. Comput. Aided Des., 30(5):333-341, 1998. URL: https://doi.org/10.1016/S0010-4485(97)00082-1.
  7. Nvidia Corporation. CUDA Zone. https://developer.nvidia.com/cuda-zone, 2020. [Online; accessed 17-March-2020]. URL: https://developer.nvidia.com/cuda-zone.
  8. Nvidia Corporation. Thrust. https://developer.nvidia.com/thrust, 2020. [Online; accessed 17-March-2020]. URL: https://developer.nvidia.com/thrust.
  9. Tran Kai Frank Da, Sébastien Loriot, and Mariette Yvinec. 3D alpha shapes. In CGAL User and Reference Manual. CGAL Editorial Board, 4.11 edition, 2017. URL: http://doc.cgal.org/4.11/Manual/packages.html#PkgAlphaShapes3Summary.
  10. Joe Dundas, Zheng Ouyang, Jeffery Tseng, T. Andrew Binkowski, Yaron Turpaz, and Jie Liang. CASTp: computed atlas of surface topography of proteins with structural and topographical mapping of functionally annotated residues. Nucleic Acids Research, 34(Web-Server-Issue):116-118, 2006. URL: https://doi.org/10.1093/nar/gkl282.
  11. H. Edelsbrunner. Weighted alpha shapes. University of Illinois at Urbana-Champaign, Department of Computer Science, 1992. Google Scholar
  12. H. Edelsbrunner and P. Koehl. The geometry of biomolecular solvation. In Discrete and Computational Geometry, pages 243-275. MSRI Publications, 2005. Google Scholar
  13. Herbert Edelsbrunner. Geometry and Topology for Mesh Generation, volume 7 of Cambridge monographs on applied and computational mathematics. Cambridge University Press, 2001. Google Scholar
  14. Herbert Edelsbrunner. Alpha shapes - a survey. In R. van de Weygaert, G. Vegter, J. Ritzerveld, and V. Icke, editors, Tesellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings, 2011. Google Scholar
  15. Herbert Edelsbrunner and John Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. URL: http://www.ams.org/bookstore-getitem/item=MBK-69.
  16. Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Trans. Inf. Theory, 29(4):551-558, 1983. URL: https://doi.org/10.1109/TIT.1983.1056714.
  17. Herbert Edelsbrunner and Ernst P. Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph., 9(1):66-104, 1990. URL: https://doi.org/10.1145/77635.77639.
  18. Herbert Edelsbrunner and Ernst P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graph., 13(1):43-72, 1994. URL: https://doi.org/10.1145/174462.156635.
  19. Herbert Edelsbrunner and Raimund Seidel. Voronoi diagrams and arrangements. Discret. Comput. Geom., 1:25-44, 1986. URL: https://doi.org/10.1007/BF02187681.
  20. Herbert Edelsbrunner and Nimish R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15(3):223-241, 1996. URL: https://doi.org/10.1007/BF01975867.
  21. Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica, 7(4):381-413, 1992. URL: https://doi.org/10.1007/BF01758770.
  22. Dan Halperin and Mark H. Overmars. Spheres, molecules, and hidden surface removal. Comput. Geom., 11(2):83-102, 1998. URL: https://doi.org/10.1016/S0925-7721(98)00023-6.
  23. Michael Krone, Barbora Kozlíková, Norbert Lindow, Marc Baaden, Daniel Baum, Július Parulek, Hans-Christian Hege, and Ivan Viola. Visual analysis of biomolecular cavities: State of the art. Comput. Graph. Forum, 35(3):527-551, 2016. URL: https://doi.org/10.1111/cgf.12928.
  24. J. Liang, H. Edelsbrunner, P. Fu, P.V. Sudhakar, and S. Subramaniam. Analytical shape computation of macromolecules: I. molecular area and volume through alpha shape. Proteins Structure Function and Genetics, 33(1):1-17, 1998. Google Scholar
  25. J. Liang, H. Edelsbrunner, P. Fu, P.V. Sudhakar, and S. Subramaniam. Analytical shape computation of macromolecules: II. inaccessible cavities in proteins. Proteins Structure Function and Genetics, 33(1):18-29, 1998. Google Scholar
  26. J. Liang, H. Edelsbrunner, and C. Woodward. Anatomy of protein pockets and cavities. Protein Science, 7(9):1884-1897, 1998. Google Scholar
  27. Paul Mach and Patrice Koehl. Geometric measures of large biomolecules: Surface, volume, and pockets. Journal of Computational Chemistry, 32(14):3023-3038, 2011. URL: https://doi.org/10.1002/jcc.21884.
  28. Talha Bin Masood and Vijay Natarajan. An integrated geometric and topological approach to connecting cavities in biomolecules. In Chuck Hansen, Ivan Viola, and Xiaoru Yuan, editors, 2016 IEEE Pacific Visualization Symposium, PacificVis 2016, Taipei, Taiwan, April 19-22, 2016, pages 104-111. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/PACIFICVIS.2016.7465257.
  29. Talha Bin Masood, Tathagata Ray, and Vijay Natarajan. Parallel computation of alpha complex for biomolecules. CoRR, abs/1908.05944, 2019. URL: http://arxiv.org/abs/1908.05944.
  30. Talha Bin Masood, Sankaran Sandhya, Nagasuma R. Chandra, and Vijay Natarajan. CHEXVIS: a tool for molecular channel extraction and visualization. BMC Bioinform., 16:119:1-119:19, 2015. URL: https://doi.org/10.1186/s12859-015-0545-9.
  31. Ashwin Nanjappa. Delaunay triangulation in ℝ³ on the GPU. PhD thesis, National University of Singapore, 2012. Google Scholar
  32. Donald R. Sheehy. An output-sensitive algorithm for computing weighted α-complexes. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10-12, 2015. Queen’s University, Ontario, Canada, 2015. URL: http://research.cs.queensu.ca/cccg2015/CCCG15-papers/42.pdf.
  33. Raghavendra Sridharamurthy, Talha Bin Masood, Harish Doraiswamy, Siddharth Patel, Raghavan Varadarajan, and Vijay Natarajan. Extraction of robust voids and pockets in proteins. In Lars Linsen, Bernd Hamann, and Hans-Christian Hege, editors, Visualization in Medicine and Life Sciences III, Mathematics and Visualization, pages 329-349. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-24523-2_15.
  34. David F Watson. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. The Computer Journal, 24(2):167-172, 1981. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact