Succinct de Bruijn graphs

DOI10.1007/978-3-642-33122-0_18MaRDI QIDQ4916912zbMATH OpenOpenAlexFDO

Authors Alexander Bowe, Taku Onodera, Kunihiko Sadakane, Tetsuo Shibuya

Publication date 26 April 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://id.nii.ac.jp/1013/00005806/

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20)

Recommendations

• Bidirectional variable-order de Bruijn graphs
• Linking indexing data structures to de Bruijn graphs: construction and update
• From indexing data structures to de Bruijn graphs
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Bidirectional Variable-Order de Bruijn Graphs

Cited in

(47)

• Wheeler graphs: a framework for BWT-based data structures
• FM-index of alignment with gaps
• Fixed block compression boosting in FM-indexes: theory and practice
• Computing the multi-string BWT and LCP array in external memory
• Wheeler languages
• Solving string problems on graphs using the labeled direct product
• A tale of optimizing the space taken by de Bruijn graphs
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• On the complexity of recognizing Wheeler graphs
• Lightweight merging of compressed indices based on BWT variants
• Compressed spaced suffix arrays
• A fast algorithm for the construction of universal footprinting templates in DNA
• Sparse binary relation representations for genome graph annotation
• Linking indexing data structures to de Bruijn graphs: construction and update
• Edge minimization in de Bruijn graphs
• Construction of a de Bruijn graph for assembly from a truncated suffix tree
• Bidirectional variable-order de Bruijn graphs
• Efficient construction of a compressed de Bruijn graph for pan-genome analysis
• Shifted de Bruijn graphs
• Representation of \(k\)-mer sets using spectrum-preserving string sets
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Simulating the DNA overlap graph in succinct space
• External memory BWT and LCP computation for sequence collections with applications
• Disentangled long-read de Bruijn graphs via optical maps
• Rainbowfish: a succinct colored de Bruijn graph representation
• From indexing data structures to de Bruijn graphs
• Bloom filter trie -- a data structure for pan-genome storage
• Bidirectional Variable-Order de Bruijn Graphs
• Spectrum preserving tilings enable sparse and modular reference indexing
• Compressed Weighted de Bruijn Graphs
• On representing the degree sequences of sublogarithmic-degree Wheeler graphs
• Space-Efficient Representation of Genomic k-Mer Count Tables
• Linear time construction of indexable founder block graphs
• Disk compression of k-mer sets
• An index for sequencing reads based on the colored de Bruijn graph
• Space-efficient merging of succinct de Bruijn graphs
• Space-time trade-offs for the LCP array of Wheeler DFAs
• Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time
• Comparative genomics with succinct colored de Bruijn graphs
• Fast pattern matching with epsilon transitions
• Prokrustean graph: a substring index for rapid k-mer size analysis
• A Myhill-Nerode theorem for generalized automata, with applications to pattern matching and compression
• Prefix sorting DFAs: a recursive algorithm
• Co-lexicographically ordering automata and regular languages. I
• The trie measure, revisited
• Fast pattern matching with epsilon transitions
• Generalized Wheeler automata: minimality

This page was built for publication: Succinct de Bruijn graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4916912)