{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T18:10:23Z","timestamp":1785953423337,"version":"3.56.0"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"20","license":[{"start":{"date-parts":[[2017,2,14]],"date-time":"2017-02-14T00:00:00Z","timestamp":1487030400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["294143"],"award-info":[{"award-number":["294143"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["268324"],"award-info":[{"award-number":["268324"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>In 2012, Iqbal et al. introduced the colored de Bruijn graph, a variant of the classic de Bruijn graph, which is aimed at \u2018detecting and genotyping simple and complex genetic variants in an individual or population\u2019. Because they are intended to be applied to massive population level data, it is essential that the graphs be represented efficiently. Unfortunately, current succinct de Bruijn graph representations are not directly applicable to the colored de Bruijn graph, which requires additional information to be succinctly encoded as well as support for non-standard traversal operations.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Our data structure dramatically reduces the amount of memory required to store and use the colored de Bruijn graph, with some penalty to runtime, allowing it to be applied in much larger and more ambitious sequence projects than was previously possible.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and Implementation<\/jats:title>\n                    <jats:p>https:\/\/github.com\/cosmo-team\/cosmo\/tree\/VARI<\/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\/btx067","type":"journal-article","created":{"date-parts":[[2017,2,15]],"date-time":"2017-02-15T03:58:08Z","timestamp":1487131088000},"page":"3181-3187","source":"Crossref","is-referenced-by-count":103,"title":["Succinct colored de Bruijn graphs"],"prefix":"10.1093","volume":"33","author":[{"given":"Martin D","family":"Muggli","sequence":"first","affiliation":[{"name":"Department of Computer Science, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Bowe","sequence":"additional","affiliation":[{"name":"Department of Informatics, National Institute of Informatics, Chiyoda-ku, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noelle R","family":"Noyes","sequence":"additional","affiliation":[{"name":"Department of Clinical Sciences, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul S","family":"Morley","sequence":"additional","affiliation":[{"name":"Department of Clinical Sciences, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Keith E","family":"Belk","sequence":"additional","affiliation":[{"name":"Department of Animal Sciences, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Raymond","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"School of Computer Science and Telecommunications, Diego Portales University and CEBIB, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon J","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado State University, Fort Collins, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2017,2,14]]},"reference":[{"key":"2023020207511382700_btx067-B1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1111\/j.1469-0691.2012.03860.x","article-title":"Metagenomic epidemiology: a public health need for the control of antimicrobial resistance","volume":"18","author":"Baquero","year":"2012","journal-title":"Clin. Microbiol. Infect"},{"key":"2023020207511382700_btx067-B2","doi-asserted-by":"crossref","first-page":"15.","DOI":"10.3389\/fmicb.2013.00015","article-title":"Antibiotic resistance shaping multi-level population biology of bacteria","volume":"4","author":"Baquero","year":"2013","journal-title":"Front. Microbiol"},{"key":"2023020207511382700_btx067-B3","doi-asserted-by":"crossref","first-page":"2114","DOI":"10.1093\/bioinformatics\/btu170","article-title":"Trimmomatic: a flexible trimmer for Illumina sequence data","volume":"30","author":"Bolger","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020207511382700_btx067-B4","first-page":"225","article-title":"Succinct de Bruijn graphs","author":"Bowe","year":"2012","journal-title":"Proc. WABI"},{"key":"2023020207511382700_btx067-B5","author":"Burrows","year":"1994"},{"key":"2023020207511382700_btx067-B6","doi-asserted-by":"crossref","first-page":"791.","DOI":"10.1186\/1471-2164-14-791","article-title":"Whole genome resequencing in tomato reveals variation associated with introgression and breeding events","volume":"14","author":"Causse","year":"2013","journal-title":"BMC Genomics"},{"key":"2023020207511382700_btx067-B7","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":"2023020207511382700_btx067-B8","first-page":"35","article-title":"On the representation of de Bruijn graphs","author":"Chikhi","year":"2014","journal-title":"Proc. RECOMB"},{"key":"2023020207511382700_btx067-B9","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1038\/nbt.2023","article-title":"How to apply de bruijn graphs to genome assembly","volume":"29","author":"Compeau","year":"2011","journal-title":"Nat. Biotechnol"},{"key":"2023020207511382700_btx067-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":"2023020207511382700_btx067-B11","doi-asserted-by":"crossref","first-page":"1569","DOI":"10.1093\/bioinformatics\/btv022","article-title":"KMC 2: Fast and resource-frugal k-mer counting","volume":"31","author":"Deorowicz","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020207511382700_btx067-B12","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient storage and retrieval by content and address of static files","volume":"21","author":"Elias","year":"1974","journal-title":"J. ACM"},{"key":"2023020207511382700_btx067-B13","author":"EMBL-EBI Metagenomics","year":"2016"},{"key":"2023020207511382700_btx067-B14","volume-title":"On the Number of Bits Required to Implement an Associative Memory","author":"Fano","year":"1971"},{"key":"2023020207511382700_btx067-B15","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":"2023020207511382700_btx067-B16","author":"Food and Agricultural Organization of the United Nations","year":"2016"},{"key":"2023020207511382700_btx067-B17","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1093\/jhered\/esp086","article-title":"Genome 10K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species","volume":"100","author":"Genome 10K Community of Scientists","year":"2009","journal-title":"J. Hered"},{"key":"2023020207511382700_btx067-B18","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-662-48221-6_16","article-title":"Bloom filter trie \u2013 a data structure for pan-genome storage","volume":"9289","author":"Holley","year":"2015","journal-title":"Algorithms Bioinf"},{"key":"2023020207511382700_btx067-B19","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":"2023020207511382700_btx067-B20","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":"2023020207511382700_btx067-B21","doi-asserted-by":"crossref","first-page":"e0160124.","DOI":"10.1371\/journal.pone.0160124","article-title":"Longitudinal metagenomic analysis of hospital air identifies clinically relevant microbes","volume":"11","author":"King","year":"2016","journal-title":"PLoS ONE"},{"key":"2023020207511382700_btx067-B22","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1093\/pcp\/pct181","article-title":"Genome-wide analysis of intraspecific DNA polymorphism in \u201cmicro-tom\u201d, a model cultivar of tomato (solanum lycopersicum)","volume":"55","author":"Kobayashi","year":"2014","journal-title":"Plant Cell Physiol"},{"key":"2023020207511382700_btx067-B23","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":"2023020207511382700_btx067-B24","doi-asserted-by":"crossref","first-page":"S6.","DOI":"10.1186\/1471-2164-15-S6-S6","article-title":"What is the difference between the breakpoint graph and the de Bruijn graph?","volume":"15","author":"Lin","year":"2014","journal-title":"BMC Genomics"},{"key":"2023020207511382700_btx067-B25","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1038\/nrg2778","article-title":"The population genetics of antibiotic resistance: integrating molecular mechanisms and treatment contexts","volume":"11","author":"MacLean","year":"2010","journal-title":"Nat. Rev. Genet"},{"key":"2023020207511382700_btx067-B26","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":"2023020207511382700_btx067-B27","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/gm485","article-title":"Metagenomics for pathogen detection in public health","volume":"5","author":"Miller","year":"2013","journal-title":"Genome Med"},{"key":"2023020207511382700_btx067-B28","first-page":"i80","article-title":"Misassembly detection using paired-end sequence reads and optical mapping data","volume":"31","author":"Muggli","year":"2015","journal-title":"Bioinformatics (Special Issue of ISMB 2015)"},{"key":"2023020207511382700_btx067-B29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures - a Practical Approach","author":"Navarro","year":"2016"},{"key":"2023020207511382700_btx067-B30","doi-asserted-by":"crossref","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":"2023020207511382700_btx067-B31","first-page":"60","article-title":"Practical entropy-compressed rank\/select dictionary","author":"Okanohara","year":"2007","journal-title":"Proc. ALENEX"},{"key":"2023020207511382700_btx067-B32","doi-asserted-by":"crossref","first-page":"1420","DOI":"10.1093\/bioinformatics\/bts174","article-title":"IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth","volume":"28","author":"Peng","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020207511382700_btx067-B33","doi-asserted-by":"crossref","DOI":"10.1289\/ehp.1307009","article-title":"Metagenomic frameworks for monitoring antibiotic resistance in aquatic environments","volume":"122","author":"Port","year":"2014","journal-title":"Environ. Health Perspect"},{"key":"2023020207511382700_btx067-B34","doi-asserted-by":"crossref","first-page":"43.","DOI":"10.1145\/1290672.1290680","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets","volume":"3","author":"Raman","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"2023020207511382700_btx067-B35","doi-asserted-by":"crossref","first-page":"1386.","DOI":"10.1126\/science.331.6023.1386","article-title":"Creating a buzz about insect genomes","volume":"331","author":"Robinson","year":"2011","journal-title":"Science"},{"key":"2023020207511382700_btx067-B36","first-page":"i188","article-title":"SEQuel: Improving the accuracy of genome assemblies","volume":"28","author":"Ronen","year":"2012","journal-title":"Bioinformatics (Special Issue of ISMB 2012)"},{"key":"2023020207511382700_btx067-B37","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1126\/science.1178534","article-title":"The B73 maize genome: complexity, diversity, and dynamics","volume":"326","author":"Schnable","year":"2009","journal-title":"Science"},{"key":"2023020207511382700_btx067-B38","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":"2023020207511382700_btx067-B39","doi-asserted-by":"crossref","first-page":"D1009","DOI":"10.1093\/nar\/gkm965","article-title":"The Arabidopsis information resource (TAIR): gene structure and function annotation","volume":"36","author":"Swarbreck","year":"2008","journal-title":"Nucleic Acids Res"},{"key":"2023020207511382700_btx067-B40","first-page":"D1028","article-title":"The rice annotation project database (RAP-DB): 2008 update","volume":"36","author":"Tanaka","year":"2008","journal-title":"Nucleic Acids Res"},{"key":"2023020207511382700_btx067-B41","volume-title":"National Action Plan for Combating Antibiotic-Resistant Bacteria","author":"The White House","year":"2015"},{"key":"2023020207511382700_btx067-B42","doi-asserted-by":"crossref","first-page":"107.","DOI":"10.1186\/gb-2009-10-5-107","article-title":"The 1001 genomes project for Arabidopsis thaliana","volume":"10","author":"Weigel","year":"2009","journal-title":"Genome Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/20\/3181\/49042808\/bioinformatics_33_20_3181.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/20\/3181\/49042808\/bioinformatics_33_20_3181.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T02:56:55Z","timestamp":1675306615000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/20\/3181\/2995815"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2017,2,14]]},"references-count":42,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2017,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx067","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/040071","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":[[2017,10,15]]},"published":{"date-parts":[[2017,2,14]]}}}