License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.17
URN: urn:nbn:de:0030-drops-121758
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12175/
Go to the corresponding LIPIcs Volume Portal

Masood, Talha Bin ; Ray, Tathagata ; Natarajan, Vijay

Parallel Computation of Alpha Complexes for Biomolecules

pdf-format:
LIPIcs-SoCG-2020-17.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{masood_et_al:LIPIcs:2020:12175,
  author =	{Talha Bin Masood and Tathagata Ray and Vijay Natarajan},
  title =	{{Parallel Computation of Alpha Complexes for Biomolecules}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12175},
  URN =		{urn:nbn:de:0030-drops-121758},
  doi =		{10.4230/LIPIcs.SoCG.2020.17},
  annote =	{Keywords: Delaunay triangulation, parallel algorithms, biomolecules, GPU}
}

Keywords: Delaunay triangulation, parallel algorithms, biomolecules, GPU
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020
Supplementary Material: Source code available at: https://bitbucket.org/vgl_iisc/parallelac/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI