Simulating the DNA overlap graph in succinct space

DOI10.4230/LIPICS.CPM.2019.26MaRDI QIDQ5088917zbMATH OpenFDO

Authors Diego Díaz-Domínguez, Travis Gagie, Gonzalo Navarro

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1901.10453

zbMATH Keywords

de Bruijn graphDNA sequencingoverlap graphsuccinct ordinal trees

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• An index for sequencing reads based on the colored de Bruijn graph
• From indexing data structures to de Bruijn graphs
• Linking indexing data structures to de Bruijn graphs: construction and update
• Succinct de Bruijn graphs
• Approximate All-Pairs Suffix/Prefix Overlaps

Cites work

• Compressed representations of sequences and full-text indexes
• Faster compressed suffix trees for repetitive collections
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Indexing compressed text
• Linear work suffix array construction
• Linear-time construction of suffix arrays (extended abstract)
• Replacing suffix trees with enhanced suffix arrays
• Space efficient linear time construction of suffix arrays
• Succinct de Bruijn graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets

Cited in

(5)

• Edge-outer graph embedding and the complexity of the DNA reporter strand problem
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• An index for sequencing reads based on the colored de Bruijn graph
• Space-time trade-offs for the LCP array of Wheeler DFAs
• Simple gene assembly as a rewriting of directed overlap-inclusion graphs

This page was built for publication: Simulating the DNA overlap graph in succinct space

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