Name
Abstract | ||
|---|---|---|
Sequence segmentation has gained popularity in bioinformatics and particularly in studying DNA sequences. Information theoretic models have been used in providing accurate solutions in the segmentation of DNA sequences. Existing dynamic programming approaches provide optimal solution to the segmentation problem. However, their quadratic time complexity prohibits their applicability to long sequences. In this paper, we propose a parallel approach to improve the performance of a quasilinear sequence segmentation algorithm. The target segmentation technique is a divide-and-conquer recursive algorithm that is based on information theory principles and models. We present three parallel implementations that aim at reducing the segmentation time. The first implementation uses the multithreading capabilities of CPUs. The second one is a hybrid implementation that utilizes the synergy between the CPU and the multithreading power of GPUs. The third implementation is a variation of the hybrid approach where it utilizes the concept of unified memory between the CPU and the GPU instead of the standard memory copy approach. We demonstrate the applicability of the parallel implementations by testing them on real DNA sequences and randomly generated sequences with different lengths and different number of unique elements. The results show that the hybrid CPU-GPU approach outperforms the sequential implementation with a speedup of up to 5.9X while the CPU parallel implementation provides a poor speedup of only 1.7X. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.simpat.2018.04.007 | Simulation Modelling Practice and Theory |
Keywords | Field | DocType |
CUDA,OpenMP,Recursive Sequence Segmentation,Unified Memory | Information theory,Dynamic programming,Multithreading,Central processing unit,Recursion (computer science),Segmentation,Computer science,Parallel computing,Time complexity,Speedup | Journal |
Volume | ISSN | Citations |
86 | 1569-190X | 0 |
PageRank | References | Authors |
0.34 | 20 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luay Alawneh | 1 | 70 | 9.18 |
| Emad Rawashdeh | 2 | 0 | 0.34 |
| Mahmoud Al-Ayyoub | 3 | 730 | 63.41 |
| Yaser Jararweh | 4 | 968 | 88.95 |