الفهرس 
RELATED WORKOnly 14 pages are availabe for public view
 |  | from | 109 |  |  |
| | | from | 109 | | |
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-MatAlign provides 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 alignment and the proposed parallel paradigms parallelize only the first level since the second level is inherently sequential.
The parallel algorithms are implemented using two common APIs for C++ parallel programming, which are OpenMP 2.0 for multi-core CPUs and CUDA 6.5 for multi-core GPUs. To run the CUDA parallel implementation, we used an nVIDIA GeForce GTX 860M series (Maxwell class) graphics card. This GTX 860M has nVIDIA compute capability 5.0 and consists of 5 streaming multiprocessors. Each multiprocessor has 640 cores, shared memory with size 49 KB per block, total constant memory with size 65 KB, 65536 registers, and total global memory with size 2GB. For running the OpenMP parallel implementation, we used a hyper-threaded dual-core 2.5 GHz Intel CPUs which provides at least 8 and up to 16 independent Pthreads. The results show that beside the significant improvement of the parallel implementation over the sequential one, it also shows that the multi-core GPU parallel implementation improves speedup over the multi-core CPU parallel implementation.