A Cache-Friendly BWT Layout

Abstract

The Burrows-Wheeler Transform (BWT) is a widely used succinct data structure in bioinformatics. However, one of the main concerns that researchers still face when using BWT is its processing time due to the lack of access locality. The (Last to First) LF mapping is derived from the BWT to facilitate backward searches, each step of the LF mapping tends to jump to a completely different spot of the BWT, resulting in at least one cache miss per step. Our project endeavours to minimize the processing time of BWT through the optimization of BWT layout. This objective is achieved by block partitioning and rearranging the layout of the BWT. Two proxy measures were introduced to represent the cache misses, but the reduced proxies did not correspond to an improved running time. However, the blocked partitioned BWT representation still achieved a 50% speedup with limited memory and a hard disk drive (HDD).