A representation of a compressed de Bruijn graph for pan-genome analysis that enables search

Abstract

Background: Recently, Marcus et al. (Bioinformatics 30:3476-83, 2014) proposed to use a compressed de Bruijn graph to describe the relationship between the genomes of many individuals/strains of the same or closely related species. They devised an [Formula: see text] time algorithm called splitMEM that constructs this graph directly (i.e., without using the uncompressed de Bruijn graph) based on a suffix tree, where n is the total length of the genomes and g is the length of the longest genome. Baier et al. (Bioinformatics 32:497-504, 2016) improved their result.

Results: In this paper, we propose a new space-efficient representation of the compressed de Bruijn graph that adds the possibility to search for a pattern (e.g. an allele-a variant form of a gene) within the pan-genome. The ability to search within the pan-genome graph is of utmost importance and is a design goal of pan-genome data structures.

Keywords: Backward search; Burrows–Wheeler transform; Compressed de Bruijn graph; Pan-genome analysis.

Fig. 1

The de Bruijn graph for $k=3$ and the string ACTACGTACGTACG$ is shown on the left, while its compressed counterpart is shown on the right

Fig. 2

Explicit representation of the compressed de Bruijn graph from Fig. 1

Fig. 3

Implicit representation of the compressed de Bruijn graph from Fig. 1

Fig. 4

The string $\mathit{\omega }$ must be split if the length k prefix of $c\mathit{\omega }$ is a right-maximal repeat or the length k prefix of $\mathit{\omega }$ is a left-maximal repeat

Fig. 5

The string $\mathit{\omega }$ has u as suffix and u has $P[m-k+1..m]$ as prefix