Space-efficient merging of succinct de Bruijn graphs
share
We propose a new algorithm for merging succinct representations of de Bruijn graphs introduced in [Bowe et al. WABI 2012]. Our algorithm is inspired by the approach introduced by Holt and McMillan [Bionformatics 2014, ACM-BCB 2014] for merging Burrow-Wheeler transforms. In addition to its input, our algorithm uses only four bitvectors of working space and all data is accessed sequentially making the algorithm suitable for external memory execution. Our algorithm can also merge Colored succinct de Bruijn graphs, and can compute the Variable Order succinct representation from the plain representation of the input graphs. Combining our merging algorithm with recent results on de Bruijn graph construction, we provide a space efficient procedure for building succinct representations of de Bruijn graphs for very large collections.
READ FULL TEXT