{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:33:18Z","timestamp":1773275598933,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"24","license":[{"start":{"date-parts":[[2018,6,22]],"date-time":"2018-06-22T00:00:00Z","timestamp":1529625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1618814"],"award-info":[{"award-number":["1618814"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"FONDECYT","doi-asserted-by":"publisher","award":["1171058"],"award-info":[{"award-number":["1171058"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Our source-code is publicly available at https:\/\/github.com\/csirac\/dynamicDBG under an open-source license.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty500","type":"journal-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T03:29:09Z","timestamp":1529465349000},"page":"4189-4195","source":"Crossref","is-referenced-by-count":20,"title":["Practical dynamic de Bruijn graphs"],"prefix":"10.1093","volume":"34","author":[{"given":"Victoria G","family":"Crawford","sequence":"first","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Kuhnle","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rayan","family":"Chikhi","sequence":"additional","affiliation":[{"name":"CNRS, CRIStAL, University of Lille, Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"CeBiB and School of Computer Science and Engineering, Diego Portales University, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,6,22]]},"reference":[{"key":"2023012712244460900_bty500-B1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1089\/cmb.2012.0021","article-title":"SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing","volume":"19","author":"Bankevich","year":"2012","journal-title":"J. Comput. Biol"},{"key":"2023012712244460900_bty500-B2","author":"Belazzougui","year":"2016"},{"key":"2023012712244460900_bty500-B3","author":"Belazzougui","year":"2016"},{"key":"2023012712244460900_bty500-B4","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"2023012712244460900_bty500-B5","author":"Boucher","year":"2015"},{"key":"2023012712244460900_bty500-B6","author":"Bowe","year":"2012"},{"key":"2023012712244460900_bty500-B7","author":"Burrows","year":"1994"},{"key":"2023012712244460900_bty500-B8","doi-asserted-by":"crossref","first-page":"22.","DOI":"10.1186\/1748-7188-8-22","article-title":"Space-efficient and exact de Bruijn graph representation based on a bloom filter","volume":"8","author":"Chikhi","year":"2013","journal-title":"Algorithms Mol. Biol"},{"key":"2023012712244460900_bty500-B9","author":"Chikhi","year":"2014"},{"key":"2023012712244460900_bty500-B10","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","article-title":"Succinct data structures for assembling large genomes","volume":"27","author":"Conway","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012712244460900_bty500-B11","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023012712244460900_bty500-B12","author":"Hagerup","year":"2001"},{"key":"2023012712244460900_bty500-B13","author":"Holley","year":"2015"},{"key":"2023012712244460900_bty500-B14","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","article-title":"A new algorithm for DNA sequence assembly","volume":"2","author":"Idury","year":"1995","journal-title":"J. Comput. Biol"},{"key":"2023012712244460900_bty500-B15","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet"},{"key":"2023012712244460900_bty500-B16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM J. Res. Dev"},{"key":"2023012712244460900_bty500-B17","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1093\/bioinformatics\/btv033","article-title":"MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph","volume":"31","author":"Li","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012712244460900_bty500-B18","author":"Limasset","year":"2017"},{"key":"2023012712244460900_bty500-B19","doi-asserted-by":"crossref","first-page":"3476","DOI":"10.1093\/bioinformatics\/btu756","article-title":"SplitMEM: a graphical algorithm for pan-genome analysis with suffix skips","volume":"30","author":"Marcus","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012712244460900_bty500-B20","doi-asserted-by":"crossref","first-page":"13272","DOI":"10.1073\/pnas.1121464109","article-title":"Scaling metagenome sequence assembly with probabilistic de Bruijn graphs","volume":"109","author":"Pell","year":"2012","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012712244460900_bty500-B21","author":"Peng","year":"2010"},{"key":"2023012712244460900_bty500-B22","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An Eulerian path approach to DNA fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012712244460900_bty500-B23","doi-asserted-by":"crossref","first-page":"2.","DOI":"10.1186\/1748-7188-9-2","article-title":"Using cascading bloom filters to improve the memory usage for de Brujin graphs","volume":"9","author":"Salikhov","year":"2014","journal-title":"Algorithms Mol. Biol"},{"key":"2023012712244460900_bty500-B24","doi-asserted-by":"crossref","first-page":"3506","DOI":"10.1093\/bioinformatics\/btu538","article-title":"Lordec: accurate and efficient long read error correction","volume":"30","author":"Salmela","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012712244460900_bty500-B25","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res"},{"key":"2023012712244460900_bty500-B26","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short read assembly using de Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/24\/4189\/48919718\/bioinformatics_34_24_4189.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/24\/4189\/48919718\/bioinformatics_34_24_4189.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T13:10:21Z","timestamp":1674825021000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/24\/4189\/5043010"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,6,22]]},"references-count":26,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2018,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty500","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,12,15]]},"published":{"date-parts":[[2018,6,22]]}}}