Parallel suffix sorting based on bucket pointer refinement

Suffix array is one of the most important data structures in bioinformatics. Much effort has been devoted to find efficient sequential algorithms for its construction, but little is done to introduce parallel construction algorithms. The bucket pointer refinement algorithm is one of the efficient suffix sorting algorithms that is tuned for genomic datasets. In this paper, we introduce a parallel version of this algorithm running on (shared memory) multicore computers. We present experimental results comparing our algorithms to other parallel algorithms running on similar architecture. Our program is open source and available at http://www.nubios.nileu.edu.eg/tools/ pbpr. © 2010 IEEE.