Building Large Updatable Colored de Bruijn Graphs via Merging

Recently, there has been significant amount of effort in developing space-efficient and succinct data structures for storing and building the traditional de Bruijn graph and its variants, including the colored de Bruijn graph. However, a problem not yet considered is developing a means to merge succinct representations of the de Bruijn graph--a challenge is necessary for constructing the de Bruijn graph on very-large datasets. We create VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW, for building the colored de Bruijn graph on a very-large dataset through partitioning the data into smaller subsets, building the colored de Bruijn graph using a FM-index based representation, and merging these representations in an iterative format. This last step is an algorithmic challenge for which we present an algorithm in this paper. Lastly, we demonstrate the utility of VO_SCPLOWARIC_SCPLOWMO_SCPLOWERGEC_SCPLOW by demonstrating: a four-fold reduction in working space when constructing an 8,000 color dataset, and the construction of population graph two orders of magnitude larger than previous reported methods.