A representation of a compressed de Bruijn graph for pan-genome analysis that enables search. Issue 1 (December 2016)

• Record Type: Journal Article
• Authors: Beller, Timo; Ohlebusch, Enno
• Is Part Of: Algorithms for molecular biology. Volume 11:Issue 1(2016)
• Page Start: 1
• Page End: 17
• Publication Date: 2016-12
• Subjects: Compressed de Bruijn graph -- Burrows–Wheeler transform -- Backward search -- Pan-genome analysis; Molecular biology -- Mathematical models -- Periodicals; Algorithms -- Periodicals; Bioinformatics -- Periodicals; 572.8015118
• DOI: 10.1186/s13015-016-0083-7
• Languages: English
• ISSNs: 1748-7188

Abstract

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 $$O(n\log g)$$ O ( n log g ) time algorithm called splitMEM that constructs this graph directly (i.e., without using the uncompressed de Bruijn graph) based on a suffix tree, wheren is the total length of the genomes andg 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.