A massively parallel algorithm for constructing the BWT of large string sets

Jacopo Pantaleoni
arXiv:1410.0562 [cs.DS], (2 Oct 2014)


   author={Pantaleoni}, J.},

   title={"{A massively parallel algorithm for constructing the BWT of large string sets}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Data Structures and Algorithms, Computer Science – Distributed, Parallel, and Cluster Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



We present a new scalable, lightweight algorithm to incrementally construct the BWT and FM-index of large string sets such as those produced by Next Generation Sequencing. The algorithm is designed for massive parallelism and can effectively exploit the combination of low capacity high bandwidth memory and slower external system memory typical of GPU accelerated systems. Particularly, for a string set of n characters from an alphabet with sigma symbols, it uses a constant amount of high-bandwidth memory and at most 3n log(sigma) bits of system memory. Given that deep memory hierarchies are becoming a pervasive trait of high performance computing architectures, we believe this to be a relevant feature. The implementation can handle reads of arbitrary length and is up to 2 and respectively 6.5 times faster than state-of-the-art for short and long genomic reads.
Rating: 0.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: