{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T17:42:23Z","timestamp":1770486143079,"version":"3.49.0"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Low-cost genome sequencing gives unprecedented complete information about the genetic structure of populations, and a population graph captures the variations between many individuals of a population. Recently, Marcus et\u00a0al. proposed to use a compressed de Bruijn graph for representing an entire population of genomes. They devised an O(nlogg) time algorithm called splitMEM that constructs this graph directly (i.e. without using the uncompressed de Bruijn graph) based on a suffix tree, where n is the total length of the genomes and g is the length of the longest genome. Since the applicability of their algorithm is limited to rather small datasets, there is a strong need for space-efficient construction algorithms.<\/jats:p>\n               <jats:p>Results: We present two algorithms that outperform splitMEM in theory and in practice. The first implements a novel linear-time suffix tree algorithm by means of a compressed suffix tree. The second algorithm uses the Burrows\u2013Wheeler transform to build the compressed de Bruijn graph in O(nlog\u03c3) time, where \u03c3 is the size of the alphabet. To demonstrate the scalability of the algorithms, we applied it to seven human genomes.<\/jats:p>\n               <jats:p>Availability and implementation: \u00a0https:\/\/www.uni-ulm.de\/in\/theo\/research\/seqana\/ \u00a0.<\/jats:p>\n               <jats:p>Contact: \u00a0Enno.Ohlebusch@uni-ulm.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv603","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T00:20:03Z","timestamp":1445905203000},"page":"497-504","source":"Crossref","is-referenced-by-count":58,"title":["Graphical pan-genome analysis with compressed suffix trees and the Burrows\u2013Wheeler transform"],"prefix":"10.1093","volume":"32","author":[{"given":"Uwe","family":"Baier","sequence":"first","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"Beller","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,10,26]]},"reference":[{"key":"2023020110323711200_btv603-B1","first-page":"40","article-title":"Efficient construction of a compressed de Bruijn graph for pan-genome analysis","author":"Beller","year":"2015"},{"key":"2023020110323711200_btv603-B2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jda.2012.07.007","article-title":"Computing the longest common prefix array based on the Burrows-Wheeler transform","volume":"18","author":"Beller","year":"2013","journal-title":"J. Discrete Algorithms"},{"key":"2023020110323711200_btv603-B3","first-page":"5","article-title":"Space-efficient construction of the Burrows-Wheeler transform","author":"Beller","year":"2013"},{"key":"2023020110323711200_btv603-B4","first-page":"89","article-title":"From indexing data structures to de Bruijn graphs","author":"Cazaux","year":"2014"},{"key":"2023020110323711200_btv603-B5","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1038\/ng.3257","article-title":"Improved genome inference in the MHC using a population reference graph","volume":"47","author":"Dilthey","year":"2015","journal-title":"Nat. Genet."},{"key":"2023020110323711200_btv603-B6","first-page":"326","article-title":"From theory to practice: plug and play with succinct data structures","author":"Gog","year":"2014"},{"key":"2023020110323711200_btv603-B7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"Gusfield","year":"1997"},{"key":"2023020110323711200_btv603-B8","first-page":"217","article-title":"Bloom filter trie\u2014a data structure for pan-genome storage","author":"Holley","year":"2015"},{"key":"2023020110323711200_btv603-B9","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De\u00a0novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"key":"2023020110323711200_btv603-B10","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":"2023020110323711200_btv603-B11","first-page":"424","article-title":"Faster compressed suffix trees for repetitive text collections","author":"Navarro","year":"2014"},{"key":"2023020110323711200_btv603-B12","volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction","author":"Ohlebusch","year":"2013"},{"key":"2023020110323711200_btv603-B13","article-title":"Mapping to a reference genome structure","author":"Paten","year":"2014"},{"key":"2023020110323711200_btv603-B14","doi-asserted-by":"crossref","first-page":"3499","DOI":"10.1093\/bioinformatics\/btu438","article-title":"Journaled string tree\u2014a scalable data structure for analyzing thousands of similar genomes on your laptop","volume":"30","author":"Rahn","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020110323711200_btv603-B15","doi-asserted-by":"crossref","first-page":"6881","DOI":"10.1128\/JB.00619-08","article-title":"The pangenome structure of Escherichia coli: comparative genomic analysis of E. coli commensal and pathogenic isolates","volume":"190","author":"Rasko","year":"2008","journal-title":"J. Bacteriol."},{"key":"2023020110323711200_btv603-B16","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1038\/msb.2011.54","article-title":"AlleleSeq: analysis of allele-specific expression and binding in a network framework","volume":"7","author":"Rozowsky","year":"2011","journal-title":"Mol. Syst. Biol."},{"key":"2023020110323711200_btv603-B17","doi-asserted-by":"crossref","first-page":"R98","DOI":"10.1186\/gb-2009-10-9-r98","article-title":"Simultaneous alignment of short reads against multiple genomes","volume":"10","author":"Schneeberger","year":"2009","journal-title":"Genome Biol."},{"key":"2023020110323711200_btv603-B18","article-title":"Large-scale search of transcriptomic read sets with sequence Bloom trees","author":"Solomon","year":"2015","journal-title":"bioRxiv"},{"key":"2023020110323711200_btv603-B19","doi-asserted-by":"crossref","first-page":"13950","DOI":"10.1073\/pnas.0506758102","article-title":"Genome analysis of multiple pathogenic isolates of Streptococcus agalactiae: implications for the microbial \u201cpan-genome\u201d","volume":"102","author":"Tettelin","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/4\/497\/49017634\/bioinformatics_32_4_497.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/4\/497\/49017634\/bioinformatics_32_4_497.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:54:26Z","timestamp":1675288466000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/4\/497\/1743785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,26]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv603","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,2,15]]},"published":{"date-parts":[[2015,10,26]]}}}