2016/02/10 by Timo Beller, Beller, Timo, Enno Ohlebusch +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Machine Learning in Bioinformatics #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.03333
Submitted to Algorithmica special issue of CPM2015
arxiv created 2016/02/10 · openalex publication_date 2016/02/10 · arxiv updated 2016/02/11 · openalex created_date 2022/09/18 · openalex updated_date 2026/07/28
Recently, Marcus et al. (Bioinformatics 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) 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. In this paper, we present a construction algorithm that outperforms their algorithm in theory and in practice. Moreover, 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.