Developing a Parallel Algorithm for Protein 3D Structure Comparison and Classification

Abstract

The importance of pairwise protein three-dimensional (3D) structure comparison process in structural bioinformatics has become vital. However, the complexity of this process is categorized as non-deterministic polynomial-time hard (NP-hard) which forced bioinformaticians to develop different algorithms to overcome the heavy computational execution time. Still, most of these algorithms tend to achieve accurate comparison results regardless of computational execution time. In this thesis, we propose a parallel algorithm, PTM-MatAlign, which is an enhanced and accelerated version of Matrix Alignment (MatAlign). This proposed algorithm is designed to use Template Modeling Score (TM-score) in the comparison process instead of the MatAlign regular score function. Also PTM-MatAlignprovides two parallel paradigms; one is built to run on NVIDIA Graphical Processing Units (GPUs) using Compute Unified Device Architecture (CUDA) programming model and the other one is built to run on multi-core CPUs using Open Multi-Processing (OpenMP). Moreover, the comparison process is based on two-level pairwise alignmentand the proposed parallel paradigms parallelize only the first level since the second level is inherently sequential.