{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T11:23:07Z","timestamp":1779362587720,"version":"3.51.4"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Second-generation sequencing technology makes it feasible for many researches to obtain enough sequence reads to attempt the de novo assembly of higher eukaryotes (including mammals). De novo assembly not only provides a tool for understanding wide scale biological variation, but within human biomedicine, it offers a direct way of observing both large-scale structural variation and fine-scale sequence variation. Unfortunately, improvements in the computational feasibility for de novo assembly have not matched the improvements in the gathering of sequence data. This is for two reasons: the inherent computational complexity of the problem and the in-practice memory requirements of tools.<\/jats:p>\n               <jats:p>Results: In this article, we use entropy compressed or succinct data structures to create a practical representation of the de Bruijn assembly graph, which requires at least a factor of 10 less storage than the kinds of structures used by deployed methods. Moreover, because our representation is entropy compressed, in the presence of sequencing errors it has better scaling behaviour asymptotically than conventional approaches. We present results of a proof-of-concept assembly of a human genome performed on a modest commodity server.<\/jats:p>\n               <jats:p>Availability: Binaries of programs for constructing and traversing the de Bruijn assembly graph are available from http:\/\/www.genomics.csse.unimelb.edu.au\/succinctAssembly.<\/jats:p>\n               <jats:p>Contact: \u00a0tom.conway@nicta.com.au<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq697","type":"journal-article","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T01:29:49Z","timestamp":1295400589000},"page":"479-486","source":"Crossref","is-referenced-by-count":122,"title":["Succinct data structures for assembling large genomes"],"prefix":"10.1093","volume":"27","author":[{"given":"Thomas C.","family":"Conway","sequence":"first","affiliation":[{"name":"NICTA Victoria Research Laboratory, Department of Computer Science and Engineering, The University of Melbourne, Parkville, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew J.","family":"Bromage","sequence":"additional","affiliation":[{"name":"NICTA Victoria Research Laboratory, Department of Computer Science and Engineering, The University of Melbourne, Parkville, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2011,1,17]]},"reference":[{"key":"2023012511573571300_B1","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1109\/ICDE.2010.5447858","article-title":"Fast in-memory xpath search over compressed text and tree indexes","volume-title":"Data Engineering (ICDE), 2010 IEEE 26th International Conference on Long Beach","author":"Arroyuelo","year":"2010"},{"key":"2023012511573571300_B2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1038\/nature07517","article-title":"Accurate whole human genome sequencing using reversible terminator chemistry","volume":"456","author":"Bentley","year":"2008","journal-title":"Nature"},{"key":"2023012511573571300_B3","first-page":"122","article-title":"Directly addressable variable-length codes","volume-title":"SPIRE","author":"Brisaboa","year":"2009"},{"key":"2023012511573571300_B4","first-page":"118","article-title":"A fast and compact web graph representation","volume-title":"SPIRE","author":"Claude","year":"2007"},{"key":"2023012511573571300_B5","first-page":"176","article-title":"Practical rank\/select queries over arbitrary sequences","volume-title":"SPIRE","author":"Claude","year":"2008"},{"key":"2023012511573571300_B6","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":"2023012511573571300_B7","first-page":"271","article-title":"Space efficient hash tables with worst case constant access time","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Fotakis","year":"2003"},{"key":"2023012511573571300_B8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-1-60327-563-7_5","article-title":"Applications of ultra-high-throughput sequencing","volume":"553","author":"Fox","year":"2009","journal-title":"Methods Mol. Biol."},{"key":"2023012511573571300_B9","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1112\/jlms\/s1-21.3.167","article-title":"Normal recurring decimals","volume":"s1-21","author":"Good","year":"1946","journal-title":"J. London Math. Soc."},{"key":"2023012511573571300_B10","first-page":"505","article-title":"Succinct data structures for searchable partial sums","volume-title":"ISAAC","author":"Hon","year":"2003"},{"key":"2023012511573571300_B11","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."},{"issue":"Suppl. 1","key":"2023012511573571300_B12","doi-asserted-by":"crossref","first-page":"S14","DOI":"10.1186\/1471-2105-10-S1-S14","article-title":"Parallel short sequence assembly of transcriptomes","volume":"10","author":"Jackson","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012511573571300_B13","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","article-title":"Space-efficient static trees and graphs","volume-title":"SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science","author":"Jacobson","year":"1989"},{"key":"2023012511573571300_B14","doi-asserted-by":"crossref","first-page":"1601","DOI":"10.1089\/cmb.2008.0146","article-title":"Computation of rank and select functions on hierarchical binary string and its application to genome mapping problems for short-read dna sequences","volume":"16","author":"Kimura","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012511573571300_B15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367072","article-title":"Dynamic entropy-compressed sequences and full-text indexes","volume":"4","author":"M\u00e4kinen","year":"2008","journal-title":"ACM Trans. Algorithms"},{"key":"2023012511573571300_B16","first-page":"289","article-title":"Computability of models for sequence assembly","volume-title":"WABI","author":"Medvedev","year":"2007"},{"key":"2023012511573571300_B17","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","article-title":"Assembly algorithms for next-generation sequencing data","volume":"95","author":"Miller","year":"2010","journal-title":"Genomics"},{"key":"2023012511573571300_B18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0935-6","volume-title":"Compression and Coding Algorithms","author":"Moffat","year":"2002"},{"key":"2023012511573571300_B19","article-title":"Practical entropy-compressed rank\/select dictionary","author":"Okanohara","year":"2006","journal-title":"CoRR"},{"key":"2023012511573571300_B20","first-page":"122","article-title":"Cuckoo hashing","volume":"2161","author":"Pagh","year":"2001","journal-title":"Lect. Notes Comput. Sci."},{"key":"2023012511573571300_B21","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":"2023012511573571300_B22","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":"2023012511573571300_B23","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1093\/bioinformatics\/btq153","article-title":"Structural variation analysis with strobe reads","volume":"26","author":"Ritz","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012511573571300_B24","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":"2023012511573571300_B25","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\/27\/4\/479\/48865058\/bioinformatics_27_4_479.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/479\/48865058\/bioinformatics_27_4_479.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:45:41Z","timestamp":1674650741000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/4\/479\/198367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,17]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq697","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,15]]},"published":{"date-parts":[[2011,1,17]]}}}