Abstract | ||
---|---|---|
Biological frequent patterns usually correspond to the important function (or structure) in biological sequences. Along with the rapid growth of biological sequences, it is significant to find frequent patterns over a large bio-sequence efficiently. However, most of existing algorithms need to produce lots of short patterns or projected databases, which influence the efficiency badly and also increase the cost of space. Graphics processing units (GPUs) embracing many core computing devices, have been extensively applied to accelerate computation performance in many areas. In order to meet the demand of biologists, we redefine the frequent pattern problem with length constraints for finding frequent patterns. We present pruning optimization method for the serial algorithm (POSA), and based on this technique, we propose a parallel algorithm (POPA) which not only reduces the time complexity with a low space cost but also obtains better performance on CUDA. To validate the presented algorithms, we implemented the algorithms on multiple-core CPU and various GPU devices. Also, CUDA optimization techniques are applied to speed up calculation in the paper. Finally, experimental results show that compared with the serial algorithm on CPU with six cores, POSA achieves 1.2~4.5 speedup, and POPA gains 3~20 speedup. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/PADSW.2014.7097865 | ICPADS |
Keywords | Field | DocType |
cuda optimization technique,graphics processing unit,popa parallel algorithm,time complexity,pruning optimization method for the serial algorithm,frequent pattern,pattern classification,graphics processing units,gpu acceleration,biological frequent pattern,cuda,many core computing device,parallel algorithms,compute unified device architecture,large biological sequence,biological sequence,acceleration,bioinformatics,posa | Graphics,CUDA,Computer science,Parallel algorithm,Parallel computing,Real-time computing,General-purpose computing on graphics processing units,Acceleration,Time complexity,Speedup,Computation | Conference |
ISSN | Citations | PageRank |
1521-9097 | 0 | 0.34 |
References | Authors | |
12 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shufang Du | 1 | 0 | 1.01 |
Longjiang Guo | 2 | 177 | 26.73 |
Chunyu Ai | 3 | 195 | 16.30 |
Jinbao Li | 4 | 251 | 39.56 |
Meirui Ren | 5 | 21 | 7.30 |
Yahong Guo | 6 | 1 | 1.02 |