GPU Accelerated Multiple Deoxyribose Nucleic Acid Sequence Parallel Matching
Computer Science & Engineering, Sichuan University Jinjiang College, Pengshan, China, 620860
arXiv:1303.3692 [cs.DS], (15 Mar 2013)
@article{2013arXiv1303.3692L,
author={Liao}, G. and {Sun}, Q. and {Ma}, L. and {Qin}, Z.},
title={"{GPU Accelerated Multiple Deoxyribose Nucleic Acid Sequence Parallel Matching}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1303.3692},
primaryClass={"cs.DS"},
keywords={Computer Science – Data Structures and Algorithms, Computer Science – Distributed, Parallel, and Cluster Computing},
year={2013},
month={mar},
adsurl={http://adsabs.harvard.edu/abs/2013arXiv1303.3692L},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
In this paper, a contrastive evaluation of massive parallel implementations of suffix tree and suffix array to accelerate genome sequence matching are proposed based on Intel Core i7 3770K quad-core and NVIDIA GeForce GTX680 GPU(kepler architecture). Due to the more regular execution flow of the indexed binary search algorithm, the more efficient use of the cache memory and the space occupied by the suffix array index is much smaller than that of the suffix tree index, the suffix array clearly outperform the suffix tree using GPU. The suffix array is more than 99 times than that of CPU serial implementation. Simultaneously, the space occupation approximately 20%~30% relative to that of suffix tree. The experimental results show that the parallel matching algorithm with respect to suffix array is an efficient approach to high performance bioinformatics applications.
March 18, 2013 by hgpu
