BWTCP: A Parallel Method for Constructing BWT in Large Collection of Genomic Reads

Short-read alignment and assembly are fundamental procedures for analyses of DNA sequencing data. Many state-of-the-art short-read aligners employ Burrows-Wheeler transform (BWT) as an in-memory index for the reference genome. BWT has also found its use in genome assembly, for indexing the reads. In a typical data set, the volume of reads can be as large as several hundred Gigabases. Consequently, fast construction of the BWT index for reads is essential for an efficient sequence processing. In this paper, we present a parallel method called BWTCP for BWT construction at a large scale. BWTCP is characterized by its ability to harness heterogeneous computing power including multi-core CPU, multiple CPUs, and accelerators like GPU or Intel Xeon Phi. BWTCP is also featured by its novel pruning strategy. Using BWTCP, we managed to construct the BWT for 1 billion 100bp reads within 30 m using 16 compute nodes (2 CPUs per node) on Tianhe-2 Supercomputer. It significantly outperforms the baseline tool BCR, which would need 13 h to finish all processing for the same dataset. BWTCP is freely available at https://​github.​com/​hwang91/​BWTCP.