XBWTing Readsets

The FM-index is an important data structure in combinatorial pattern matching and bioinformatics, that has been generalized from indexing single strings to indexing collections of strings, labelled trees, de Bruijn graphs and Wheeler graphs. To generalize the FM-index to collections of strings and to labelled trees, researchers generalized the Burrows-Wheeler Transform (BWT) to the Extended BWT (EBWT) and the eXtended BWT (XBWT), respectively. Although one of the EBWT's main applications is compressing and indexing DNA readsets, we show in this paper that when the reads have been assembled or when they align well to a reference genome, then it is possible to use that assembled or reference genome to produce a smaller compressed index. To do this, we graft the reads onto the genome and store the resulting labelled tree with the XBWT. For an {\it E.\ coli} readset, for example, our experiments show that eliminating separators characters from the EBWT reduces the number of runs by 16%, from 105.3 million to 88.3 million, and using the XBWT reduces it by a further 8.3%, to 80.9 million.