{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T00:36:25Z","timestamp":1774312585385,"version":"3.50.1"},"reference-count":53,"publisher":"Oxford University Press (OUP)","issue":"24","license":[{"start":{"date-parts":[[2016,12,20]],"date-time":"2016-12-20T00:00:00Z","timestamp":1482192000000},"content-version":"vor","delay-in-days":90,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DBI-1356529, CCF-1439057, IIS-1453527, IIS-1421908"],"award-info":[{"award-number":["DBI-1356529, CCF-1439057, IIS-1453527, IIS-1421908"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>de Bruijn graphs have been proposed as a data structure to facilitate the analysis of related whole genome sequences, in both a population and comparative genomic settings. However, current approaches do not scale well to many genomes of large size (such as mammalian genomes).<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this article, we present TwoPaCo, a simple and scalable low memory algorithm for the direct construction of the compacted de Bruijn graph from a set of complete genomes. We demonstrate that it can construct the graph for 100 simulated human genomes in less than a day and eight real primates in\u2009&amp;lt;\u20092\u2009h, on a typical shared-memory machine. We believe that this progress will enable novel biological analyses of hundreds of mammalian-sized genomes.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and Implementation<\/jats:title>\n                  <jats:p>Our code and data is available for download from github.com\/medvedevgroup\/TwoPaCo.<\/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\/btw609","type":"journal-article","created":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T00:28:33Z","timestamp":1474590513000},"page":"4024-4032","source":"Crossref","is-referenced-by-count":80,"title":["TwoPaCo: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes"],"prefix":"10.1093","volume":"33","author":[{"given":"Ilia","family":"Minkin","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Son","family":"Pham","sequence":"additional","affiliation":[{"name":"BioTuring Inc., San Diego, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, USA"},{"name":"Department of Biochemistry and Molecular Biology, The Pennsylvania State University, University Park, PA, USA"},{"name":"Genomic Sciences Institute of the Huck, The Pennsylvania State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"2023020301104805400_btw609-B1","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature09534","article-title":"A map of human genome variation from population-scale sequencing","volume":"467","author":"1000 Genomes Project Consortium","year":"2010","journal-title":"Nature"},{"key":"2023020301104805400_btw609-B2","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1093\/bioinformatics\/btv603","article-title":"Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform","volume":"32","author":"Baier","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B3","article-title":"Succinct colored de Bruijn graphs","author":"Belk","year":"2016","journal-title":"bioRxiv"},{"key":"2023020301104805400_btw609-B4","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-319-19929-0_4","volume-title":"Combinatorial Pattern Matching","author":"Beller","year":"2015"},{"key":"2023020301104805400_btw609-B5","first-page":"1","article-title":"A representation of a compressed de Bruijn graph for pan-genome analysis that enables search","volume":"11","author":"Beller","year":"2016","journal-title":"arXiv Preprint arXiv:1602.03333"},{"key":"2023020301104805400_btw609-B6","doi-asserted-by":"crossref","first-page":"3515","DOI":"10.1093\/bioinformatics\/btu578","article-title":"String graph construction using incremental hashing","volume":"30","author":"Ben-Bassat","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B7","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":"2023020301104805400_btw609-B8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-3-642-33122-0_18","volume-title":"Algorithms in Bioinformatics","author":"Bowe","year":"2012"},{"key":"2023020301104805400_btw609-B9","doi-asserted-by":"crossref","DOI":"10.1038\/ncomms10063","article-title":"Rapid antibiotic-resistance predictions from genome sequence data for staphylococcus aureus and mycobacterium tuberculosis","volume":"6","author":"Bradley","year":"2015","journal-title":"Nat. Commun"},{"key":"2023020301104805400_btw609-B10","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-07566-2_10","volume-title":"Combinatorial Pattern Matching","author":"Cazaux","year":"2014"},{"key":"2023020301104805400_btw609-B11","doi-asserted-by":"crossref","first-page":"1.","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":"2023020301104805400_btw609-B12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-319-05269-4_4","volume-title":"Research in Computational Molecular Biology","author":"Chikhi","year":"2014"},{"key":"2023020301104805400_btw609-B13","doi-asserted-by":"crossref","first-page":"i201","DOI":"10.1093\/bioinformatics\/btw279","article-title":"Compacting de Bruijn graphs from sequencing data quickly and in low memory","volume":"32","author":"Chikhi","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B14","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":"2023020301104805400_btw609-B15","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":"2023020301104805400_btw609-B16","doi-asserted-by":"crossref","first-page":"2077","DOI":"10.1101\/gr.174920.114","article-title":"Alignathon: a competitive assessment of whole-genome alignment methods","volume":"24","author":"Earl","year":"2014","journal-title":"Genome Res"},{"key":"2023020301104805400_btw609-B17","first-page":"35","volume-title":"German Conference on Bioinformatics","author":"Ernst","year":"2013"},{"key":"2023020301104805400_btw609-B18","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1038\/nature02168","article-title":"The international hapmap project","volume":"426","author":"Gibbs","year":"2003","journal-title":"Nature"},{"key":"2023020301104805400_btw609-B19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023020301104805400_btw609-B20","first-page":"659","article-title":"Genome 10K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species","volume":"100","author":"Haussler","year":"2008","journal-title":"J. Hered"},{"key":"2023020301104805400_btw609-B21","doi-asserted-by":"crossref","first-page":"1354","DOI":"10.1093\/bioinformatics\/btu030","article-title":"BLESS: bloom filter-based error correction solution for high-throughput sequencing reads","volume":"30","author":"Heo","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B22","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-662-48221-6_16","volume-title":"Algorithms in Bioinformatics","author":"Holley","year":"2015"},{"key":"2023020301104805400_btw609-B23","doi-asserted-by":"crossref","first-page":"i361","DOI":"10.1093\/bioinformatics\/btt215","article-title":"Short read alignment with populations of genomes","volume":"29","author":"Huang","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B24","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":"2023020301104805400_btw609-B25","doi-asserted-by":"crossref","first-page":"1320","DOI":"10.1126\/science.1253451","article-title":"Whole-genome analyses resolve early branches in the tree of life of modern birds","volume":"346","author":"Jarvis","year":"2014","journal-title":"Science"},{"key":"2023020301104805400_btw609-B26","doi-asserted-by":"crossref","first-page":"149.","DOI":"10.1186\/1471-2105-15-149","article-title":"FIGG: simulating populations of whole genome sequences for heterogeneous data analyses","volume":"15","author":"Killcoyne","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020301104805400_btw609-B27","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1146\/annurev-animal-090414-014900","article-title":"The genome 10k project: a way forward","volume":"3","author":"Koepfli","year":"2015","journal-title":"Annu. Rev. Anim. Biosci"},{"key":"2023020301104805400_btw609-B28","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","article-title":"Multiple sequence alignment using partial order graphs","volume":"18","author":"Lee","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B29","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1016\/j.csl.2009.12.001","article-title":"Recursive n-gram hashing is pairwise independent, at best","volume":"24","author":"Lemire","year":"2010","journal-title":"Comput. Speech Lang"},{"key":"2023020301104805400_btw609-B30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-016-1103-9","article-title":"Read mapping on de Bruijn graphs","volume":"17","author":"Limasset","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023020301104805400_btw609-B31","doi-asserted-by":"crossref","first-page":"i174","DOI":"10.1093\/bioinformatics\/btw266","article-title":"deBWT: parallel construction of Burrows\u2013Wheeler Transform for large collection of genomes with de Bruijn-branch encoding","volume":"32","author":"Liu","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B32","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":"2023020301104805400_btw609-B33","article-title":"Computational pan-genomics: status, promises and challenges","author":"Marschall","year":"2016","journal-title":"bioRxiv"},{"key":"2023020301104805400_btw609-B34","doi-asserted-by":"crossref","first-page":"333.","DOI":"10.1186\/1471-2105-12-333","article-title":"Efficient counting of k-mers in dna sequences using a bloom filter","volume":"12","author":"Melsted","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023020301104805400_btw609-B35","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":"2023020301104805400_btw609-B36","doi-asserted-by":"crossref","DOI":"10.12688\/f1000research.2-258.v1","article-title":"C-sibelia: an easy-to-use and highly accurate tool for bacterial genome comparison","volume":"2","author":"Minkin","year":"2013","journal-title":"F1000Research"},{"key":"2023020301104805400_btw609-B37","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-642-40453-5_17","volume-title":"Algorithms in Bioinformatics","author":"Minkin","year":"2013"},{"key":"2023020301104805400_btw609-B38","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher","year":"2005"},{"key":"2023020301104805400_btw609-B39","volume-title":"Java Threads","author":"Oaks","year":"2004"},{"key":"2023020301104805400_btw609-B40","author":"Paten","year":"2014"},{"key":"2023020301104805400_btw609-B41","doi-asserted-by":"crossref","first-page":"2509","DOI":"10.1093\/bioinformatics\/btq465","article-title":"DRIMM-Synteny: decomposing genomes into evolutionary conserved segments","volume":"26","author":"Pham","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B42","doi-asserted-by":"crossref","first-page":"2336","DOI":"10.1101\/gr.2657504","article-title":"A novel method for multiple alignment of sequences with repeated and shuffled elements","volume":"14","author":"Raphael","year":"2004","journal-title":"Genome Res"},{"key":"2023020301104805400_btw609-B43","volume-title":"Intel Threading Building Blocks: Outfitting C\u2009++ for Multi-Core Processor Parallelism","author":"Reinders","year":"2007"},{"key":"2023020301104805400_btw609-B44","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1093\/bioinformatics\/btt020","article-title":"Dsk: k-mer counting with very low memory usage","volume":"29","author":"Rizk","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B45","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/1471-2105-15-S9-S7","article-title":"Fast lossless compression via cascading Bloom filters","volume":"15","author":"Rozov","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020301104805400_btw609-B46","first-page":"364","volume-title":"Algorithms in Bioinformatics, Volume 8126 of Lecture Notes in Computer Science","author":"Salikhov","year":"2013"},{"key":"2023020301104805400_btw609-B47","doi-asserted-by":"crossref","first-page":"1.","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":"2023020301104805400_btw609-B48","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1101\/gr.101360.109","article-title":"Assembly of large genomes using second-generation sequencing","volume":"20","author":"Schatz","year":"2010","journal-title":"Genome Res"},{"key":"2023020301104805400_btw609-B49","doi-asserted-by":"crossref","first-page":"i367","DOI":"10.1093\/bioinformatics\/btq217","article-title":"Efficient construction of an assembly string graph using the fm-index","volume":"26","author":"Simpson","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020301104805400_btw609-B50","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","article-title":"Indexing graphs for path queries with applications in genome research","volume":"11","author":"Sir\u00e9n","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020301104805400_btw609-B51","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1038\/nbt.3442","article-title":"Fast search of thousands of short-read sequencing experiments","volume":"34","author":"Solomon","year":"2016","journal-title":"Nat. Biotechnol"},{"key":"2023020301104805400_btw609-B52","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1089\/cmb.2012.0058","article-title":"A de Bruijn graph approach to the quantification of closely-related genomes in a microbial community","volume":"19","author":"Wang","year":"2012","journal-title":"J. Comput. Biol"},{"key":"2023020301104805400_btw609-B53","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1093\/bioinformatics\/btv510","article-title":"Utilizing de Bruijn graph of metagenome assembly for metatranscriptome analysis","volume":"32","author":"Ye","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/24\/4024\/49042096\/bioinformatics_33_24_4024.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/24\/4024\/49042096\/bioinformatics_33_24_4024.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T01:11:27Z","timestamp":1675386687000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/24\/4024\/2725383"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2016,9,21]]},"references-count":53,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2017,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw609","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,12,15]]},"published":{"date-parts":[[2016,9,21]]}}}