{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:33:58Z","timestamp":1772138038823,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T00:00:00Z","timestamp":1590624000000},"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":"NSF","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\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["R01AI141810"],"award-info":[{"award-number":["R01AI141810"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["319454"],"award-info":[{"award-number":["319454"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["323233"],"award-info":[{"award-number":["323233"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>The de Bruijn graph is one of the fundamental data structures for analysis of high throughput sequencing data. In order to be applicable to population-scale studies, it is essential to build and store the graph in a space- and time-efficient manner. In addition, due to the ever-changing nature of population studies, it has become essential to update the graph after construction, e.g. add and remove nodes and edges. Although there has been substantial effort on making the construction and storage of the graph efficient, there is a limited amount of work in building the graph in an efficient and mutable manner. Hence, most space efficient data structures require complete reconstruction of the graph in order to add or remove edges or nodes.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this article, we present DynamicBOSS, a succinct representation of the de Bruijn graph that allows for an unlimited number of additions and deletions of nodes and edges. We compare our method with other competing methods and demonstrate that DynamicBOSS is the only method that supports both addition and deletion and is applicable to very large samples (e.g. greater than 15 billion k-mers). Competing dynamic methods, e.g. FDBG cannot be constructed on large scale datasets, or cannot support both addition and deletion, e.g. BiFrost.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>DynamicBOSS is publicly available at https:\/\/github.com\/baharpan\/dynboss.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa546","type":"journal-article","created":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T15:19:29Z","timestamp":1590074369000},"page":"1946-1952","source":"Crossref","is-referenced-by-count":13,"title":["Succinct dynamic de Bruijn graphs"],"prefix":"10.1093","volume":"37","author":[{"given":"Bahar","family":"Alipanahi","sequence":"first","affiliation":[{"name":"Department of Computer and Information Science and Engineering, College of Engineering, University of Florida , Gainesville, FL 32611, USA"}]},{"given":"Alan","family":"Kuhnle","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Florida State University , Tallahassee, FL 32306, USA"}]},{"given":"Simon J","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology, University of Helsinki , Helsinki 00014, Finland"}]},{"given":"Leena","family":"Salmela","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology, University of Helsinki , Helsinki 00014, Finland"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering, College of Engineering, University of Florida , Gainesville, FL 32611, USA"}]}],"member":"286","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"2023061402422092300_btaa546-B1","author":"Almodaresi","year":"2017"},{"key":"2023061402422092300_btaa546-B2","doi-asserted-by":"crossref","first-page":"1479","DOI":"10.1007\/s10115-018-1275-x","article-title":"Compact and efficient representation of general graph databases","volume":"60","author":"\u00c1lvarez Garc\u00eda","year":"2019","journal-title":"Knowledge Inf. Syst"},{"key":"2023061402422092300_btaa546-B3","first-page":"225","author":"Bowe","year":"2012"},{"key":"2023061402422092300_btaa546-B4","author":"Burrows","year":"1994"},{"key":"2023061402422092300_btaa546-B5","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":"2023061402422092300_btaa546-B6","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":"2023061402422092300_btaa546-B7","first-page":"105","author":"Cordova","year":"2016"},{"key":"2023061402422092300_btaa546-B8","doi-asserted-by":"crossref","first-page":"4189","DOI":"10.1093\/bioinformatics\/bty500","article-title":"Practical dynamic de Bruijn graphs","volume":"34","author":"Crawford","year":"2018","journal-title":"Bioinformatics"},{"key":"2023061402422092300_btaa546-B9","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":"2023061402422092300_btaa546-B10","first-page":"504","author":"Grossi","year":"2013"},{"key":"2023061402422092300_btaa546-B11","author":"Holley","year":"2019"},{"key":"2023061402422092300_btaa546-B12","first-page":"1"},{"key":"2023061402422092300_btaa546-B13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/s13015-016-0066-8","article-title":"Bloom filter TRIE: an alignment-free and reference-free data structure for pan-genome storage","volume":"11","author":"Holley","year":"2016","journal-title":"Algorithms Mol. Biol"},{"key":"2023061402422092300_btaa546-B14","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":"2023061402422092300_btaa546-B15","first-page":"626","author":"Karasikov","year":"2020"},{"key":"2023061402422092300_btaa546-B16","first-page":"160","author":"Klitzke","year":"2016"},{"key":"2023061402422092300_btaa546-B17","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput"},{"key":"2023061402422092300_btaa546-B18","doi-asserted-by":"crossref","first-page":"i51","DOI":"10.1093\/bioinformatics\/btz350","article-title":"Building large updatable colored de bruijn graphs via merging","volume":"35","author":"Muggli","year":"2019","journal-title":"Bioinformatics"},{"key":"2023061402422092300_btaa546-B19","doi-asserted-by":"crossref","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","article-title":"Succinct colored de Bruijn graphs","volume":"33","author":"Muggli","year":"2017","journal-title":"Bioinformatics"},{"key":"2023061402422092300_btaa546-B20","author":"Mustafa","year":"2017"},{"key":"2023061402422092300_btaa546-B21","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bioinformatics\/bty632","article-title":"Dynamic compression schemes for graph coloring","volume":"35","author":"Mustafa","year":"2019","journal-title":"Bioinformatics"},{"key":"2023061402422092300_btaa546-B22"},{"key":"2023061402422092300_btaa546-B23","doi-asserted-by":"crossref","first-page":"1781","DOI":"10.1137\/130908245","article-title":"Optimal dynamic sequence representations","volume":"43","author":"Navarro","year":"2014","journal-title":"SIAM J. Comput"},{"key":"2023061402422092300_btaa546-B24","doi-asserted-by":"crossref","first-page":"e13195","DOI":"10.7554\/eLife.13195","article-title":"Resistome diversity in cattle and the environment decreases during beef production","volume":"5","author":"Noyes","year":"2016","journal-title":"eLife"},{"key":"2023061402422092300_btaa546-B25","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.cels.2018.05.021","article-title":"Mantis: a fast, small, and exact large-scale sequence-search index","volume":"7","author":"Pandey","year":"2018","journal-title":"Cell Syst"},{"key":"2023061402422092300_btaa546-B26","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":"2023061402422092300_btaa546-B27","author":"Prezza","year":"2017"},{"key":"2023061402422092300_btaa546-B28","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa546\/39269965\/btaa546.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/14\/1946\/50578827\/btaa546.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/14\/1946\/50578827\/btaa546.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T22:43:37Z","timestamp":1686696217000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/14\/1946\/5848003"}},"subtitle":[],"editor":[{"given":"Anthony","family":"Mathelier","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":28,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2021,8,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa546","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.04.01.018481","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,7,15]]},"published":{"date-parts":[[2021,7,15]]}}}