
pmid: 29939217
Abstract Motivation The de Bruijn graph is fundamental to the analysis of next generation sequencing data and so, as datasets of DNA reads grow rapidly, it becomes more important to represent de Bruijn graphs compactly while still supporting fast assembly. Previous implementations of compact de Bruijn graphs have not supported node or edge deletion, however, which is important for pruning spurious elements from the graph. Results Belazzougui et al. (2016b) recently proposed a compact and fully dynamic representation, which supports exact membership queries and insertions and deletions of both nodes and edges. In this paper, we give a practical implementation of their data structure, supporting exact membership queries and fully dynamic edge operations, as well as limited support for dynamic node operations. We demonstrate experimentally that its performance is comparable to that of state-of-the-art implementations based on Bloom filters. Availability and implementation Our source-code is publicly available at https://github.com/csirac/dynamicDBG under an open-source license.
Computational Biology, High-Throughput Nucleotide Sequencing, Sequence Analysis, DNA, Algorithms, Software, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM], Sequence Deletion
Computational Biology, High-Throughput Nucleotide Sequencing, Sequence Analysis, DNA, Algorithms, Software, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM], Sequence Deletion
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
