Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)

Design and Implementation of a Parallel PTAS for Finding Structural Motifs on Graphics Processing Units (GPUs)

Authors
Julia Ysobel Pineda1, *, Andrew Sopungco1, Jhoirene Clemente1
1Algorithms and Complexity Lab, Department of Computer Science, University of the Philippines Diliman, Quezon City, Philippines
*Corresponding author. Email: jypineda@up.edu.ph
Corresponding Author
Julia Ysobel Pineda
Available Online 29 February 2024.
DOI
10.2991/978-94-6463-388-7_20How to use a DOI?
Keywords
bioinformatics; structural motif finding problem; polynomialtime approximation scheme; PTAS; parallelization; GPU
Abstract

Protein structural motifs are recurring patterns in a set of tertiary protein structures in the 3D form. These motifs often play crucial roles in protein function, stability, and interactions. The problem is NP-hard, but a polynomial-time approximation scheme (PTAS) offers efficient solutions with some trade-offs. Previous work improved performance by optimizing subroutines and employing parallelization. The current study investigates further improvements using a two-level parallelization approach, offloading computationally-intensive SVD operations to GPUs while keeping the rest on CPU. The comparison between CPU and GPU implementations is based on speedup and parallel efficiency metrics. While the trends in results are similar, the GPU implementation exhibits significantly delayed execution times. The study provides insights into the potential benefits of the two-level parallelization approach and offers data-driven suggestions for further advancements in the solution. Overall, it aims to contribute to computational optimization in bioinformatics and explore novel methods for solving the structural motif finding problem.

Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

Volume Title
Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
Series
Atlantis Highlights in Computer Sciences
Publication Date
29 February 2024
ISBN
978-94-6463-388-7
ISSN
2589-4900
DOI
10.2991/978-94-6463-388-7_20How to use a DOI?
Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

TY  - CONF
AU  - Julia Ysobel Pineda
AU  - Andrew Sopungco
AU  - Jhoirene Clemente
PY  - 2024
DA  - 2024/02/29
TI  - Design and Implementation of a Parallel PTAS for Finding Structural Motifs on Graphics Processing Units (GPUs)
BT  - Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
PB  - Atlantis Press
SP  - 325
EP  - 341
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6463-388-7_20
DO  - 10.2991/978-94-6463-388-7_20
ID  - Pineda2024
ER  -