GPU parallelization of sequence segmentation using information theoretic models

摘要: Abstract Sequence segmentation has gained popularity in bioinformatics and particularly studying DNA sequences. Information theoretic models have been used providing accurate solutions the of Existing dynamic programming approaches provide optimal solution to problem. However, their quadratic time complexity prohibits applicability long In this paper, we propose a parallel approach improve performance quasilinear sequence algorithm. The target technique is divide-and-conquer recursive algorithm that based on information theory principles models. We present three implementations aim at reducing time. first implementation uses multithreading capabilities CPUs. second one hybrid utilizes synergy between CPU power GPUs. third variation where it concept unified memory GPU instead standard copy approach. demonstrate by testing them real sequences randomly generated with different lengths number unique elements. results show CPU-GPU outperforms sequential speedup up 5.9X while provides poor only 1.7X.