title: 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.
authors.affiliation: Institute of Theoretical Computer Science, Ulm University, James-Franck-Ring O27/537, 89069 Ulm, Germany.
authors.forename: Timo
authors.initials: T
authors.lastname: Beller
authors.affiliation: Institute of Theoretical Computer Science, Ulm University, James-Franck-Ring O27/537, 89069 Ulm, Germany.
authors.forename: Enno
authors.initials: E
authors.lastname: Ohlebusch
keywords: Backward search; Burrows–Wheeler transform; Compressed de Bruijn graph; Pan-genome analysis