A parallel design for Burrows-Wheeler transform based DNA sequences data

摘要

Aligning or assembling an enormous amount of short reads is a core step for high throughput biological applications. Based on existing indexing and pattern matching technologies, several algorithms and software have been developed. Yet, there is still a strong need to further improve the speed. In this paper, a new revised, parallel algorithm for the Burrows-Wheeler transform is presented. This is used to construct the suffix arrray of large strings such as those produced by Next Generation Sequencing. The algorithm is designed for parallelism and can effectively exploit the combination of low capacity memory and Open MP. Furthermore, the implementation is up to 2 times faster than serial algorithms.