{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T22:09:33Z","timestamp":1771625373651,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Massively parallel DNA sequencing technologies are revolutionizing genomics research. Billions of short reads generated at low costs can be assembled for reconstructing the whole genomes. Unfortunately, the large memory footprint of the existing de novo assembly algorithms makes it challenging to get the assembly done for higher eukaryotes like mammals. In this work, we investigate the memory issue of constructing de Bruijn graph, a core task in leading assembly algorithms, which often consumes several hundreds of gigabytes memory for large genomes. We propose a disk-based partition method, called Minimum Substring Partitioning (MSP), to complete the task using less than 10 gigabytes memory, without runtime slowdown. MSP breaks the short reads into multiple small disjoint partitions so that each partition can be loaded into memory, processed individually and later merged with others to form a de Bruijn graph. By leveraging the overlaps among the k-mers (substring of length k), MSP achieves astonishing compression ratio: The total size of partitions is reduced from \u0398(<jats:italic>kn<\/jats:italic>) to \u0398(<jats:italic>n<\/jats:italic>), where<jats:italic>n<\/jats:italic>is the size of the short read database, and<jats:italic>k<\/jats:italic>is the length of a<jats:italic>k<\/jats:italic>-mer. Experimental results show that our method can build de Bruijn graphs using a commodity computer for any large-volume sequence dataset.<\/jats:p>","DOI":"10.14778\/2535569.2448951","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"169-180","source":"Crossref","is-referenced-by-count":33,"title":["Memory efficient minimum substring partitioning"],"prefix":"10.14778","volume":"6","author":[{"given":"Yang","family":"Li","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara"}]},{"given":"Pegah","family":"Kamousi","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara"}]},{"given":"Fangqiu","family":"Han","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara"}]},{"given":"Shengqi","family":"Yang","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara"}]}],"member":"320","published-online":{"date-parts":[[2013,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/www.appliedbiosystems.com. http:\/\/www.appliedbiosystems.com."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/www.illumina.com. http:\/\/www.illumina.com."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/956750.956759","volume-title":"KDD","author":"Bilenko M.","year":"2003","unstructured":"M. Bilenko and R. Mooney . Adaptive duplicate detection using learnable string similarity measures . In KDD , pages 39 - 48 , 2003 . 10.1145\/956750.956759 M. Bilenko and R. Mooney. Adaptive duplicate detection using learnable string similarity measures. In KDD, pages 39-48, 2003. 10.1145\/956750.956759"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/319983.319987"},{"issue":"5","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1101\/gr.7337908","article-title":"Allpaths: de novo assembly of whole-genome shotgun microreads","volume":"18","author":"Butler J.","year":"2008","unstructured":"J. Butler , I. MacCallum , M. Kleber , I. Shlyakhter , M. Belmonte , E. Lander , C. Nusbaum , and D. Jaffe . Allpaths: de novo assembly of whole-genome shotgun microreads . Genome Research , 18 ( 5 ): 810 - 820 , 2008 . J. Butler, I. MacCallum, M. Kleber, I. Shlyakhter, M. Belmonte, E. Lander, C. Nusbaum, and D. Jaffe. Allpaths: de novo assembly of whole-genome shotgun microreads. Genome Research, 18(5):810-820, 2008.","journal-title":"Genome Research"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq697"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2001","unstructured":"T. Cormen , C. Leiserson , R. Rivest , and C. Stein . Introduction to Algorithms ( 2 nd ed.). MIT Press , 2001 . T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms (2nd ed.). MIT Press, 2001.","edition":"2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1186\/1471-2105-11-560","article-title":"Efficient parallel and out of core algorithms for constructing large bi-directed de bruijn graphs","volume":"11","author":"Kundeti V.","year":"2010","unstructured":"V. Kundeti , S. R. S, H. Dinh , M. Vaughn , and V. Thapar . Efficient parallel and out of core algorithms for constructing large bi-directed de bruijn graphs . BMC Bioinformaticse , 11 : 560 , 2010 . V. Kundeti, S. R. S, H. Dinh, M. Vaughn, and V. Thapar. Efficient parallel and out of core algorithms for constructing large bi-directed de bruijn graphs. BMC Bioinformaticse, 11:560, 2010.","journal-title":"BMC Bioinformaticse"},{"issue":"2","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1101\/gr.097261.109","article-title":"De novo assembly of human genomes with massively parallel short read sequencing","volume":"20","author":"Li R.","year":"2010","unstructured":"R. Li , H. Zhu , J. Ruan , W. Qian , X. Fang , Z. Shi , Y. Li , S. Li , G. Shan , K. Kristiansen , De novo assembly of human genomes with massively parallel short read sequencing . Genome research , 20 ( 2 ): 265 - 272 , 2010 . R. Li, H. Zhu, J. Ruan, W. Qian, X. Fang, Z. Shi, Y. Li, S. Li, G. Shan, K. Kristiansen, et al. De novo assembly of human genomes with massively parallel short read sequencing. Genome research, 20(2):265-272, 2010.","journal-title":"Genome research"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1146\/annurev.genom.9.081307.164359","article-title":"Next-generation dna sequencing methods","volume":"9","author":"Mardis E.","year":"2008","unstructured":"E. Mardis . Next-generation dna sequencing methods . Annu. Rev. Genomics Hum. Genet. , 9 : 387 - 402 , 2008 . E. Mardis. Next-generation dna sequencing methods. Annu. Rev. Genomics Hum. Genet., 9:387-402, 2008.","journal-title":"Annu. Rev. Genomics Hum. Genet."},{"key":"e_1_2_1_14_1","first-page":"12","volume-title":"WWW","author":"Metwally A.","year":"2005","unstructured":"A. Metwally , D. Agrawal , and A. E. Abbadi . Duplicate detection in click streams . In WWW , pages 12 - 21 , 2005 . 10.1145\/1060745.1060753 A. Metwally, D. Agrawal, and A. E. Abbadi. Duplicate detection in click streams. In WWW, pages 12-21, 2005. 10.1145\/1060745.1060753"},{"issue":"6","key":"e_1_2_1_15_1","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 J.","year":"2010","unstructured":"J. Miller , S. Koren , and G. Sutton . Assembly algorithms for next-generation sequencing data . Genomics , 95 ( 6 ): 315 - 327 , 2010 . J. Miller, S. Koren, and G. Sutton. Assembly algorithms for next-generation sequencing data. Genomics, 95(6):315-327, 2010.","journal-title":"Genomics"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1114"},{"issue":"5461","key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"2196","DOI":"10.1126\/science.287.5461.2196","article-title":"A whole-genome assembly of drosophila","volume":"287","author":"Myers E.","year":"2000","unstructured":"E. Myers , G. Sutton , A. Delcher , I. Dew , D. Fasulo , M. Flanigan , S. Kravitz , C. Mobarry , K. Reinert , K. Remington , A whole-genome assembly of drosophila . Science , 287 ( 5461 ): 2196 - 2204 , 2000 . E. Myers, G. Sutton, A. Delcher, I. Dew, D. Fasulo, M. Flanigan, S. Kravitz, C. Mobarry, K. Reinert, K. Remington, et al. A whole-genome assembly of drosophila. Science, 287(5461):2196-2204, 2000.","journal-title":"Science"},{"key":"e_1_2_1_18_1","first-page":"9748","volume-title":"Proceedings of the National Academy of Sciences","author":"Pevzner P.","year":"2001","unstructured":"P. Pevzner , H. Tang , and M. Waterman . An eulerian path approach to DNA fragment assembly . In Proceedings of the National Academy of Sciences , pages 9748 - 9753 , 2001 . P. Pevzner, H. Tang, and M. Waterman. An eulerian path approach to DNA fragment assembly. In Proceedings of the National Academy of Sciences, pages 9748-9753, 2001."},{"key":"e_1_2_1_19_1","volume-title":"Forge: A parallel genome assembler combining sanger and next generation sequence data","author":"Platt D.","year":"2010","unstructured":"D. Platt and D. Evers . Forge: A parallel genome assembler combining sanger and next generation sequence data . 2010 . http:\/\/combiol.org\/forge\/. D. Platt and D. Evers. Forge: A parallel genome assembler combining sanger and next generation sequence data. 2010. http:\/\/combiol.org\/forge\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth408"},{"key":"e_1_2_1_21_1","volume-title":"Contrail: Assembly of large genomes using cloud computing","author":"Schatz M.","year":"2010","unstructured":"M. Schatz , D. Sommer , D. Kelley , and M. Pop . Contrail: Assembly of large genomes using cloud computing . 2010 . http:\/\/contrail-bio.sf.net\/. M. Schatz, D. Sommer, D. Kelley, and M. Pop. Contrail: Assembly of large genomes using cloud computing. 2010. http:\/\/contrail-bio.sf.net\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq217"},{"issue":"6","key":"e_1_2_1_23_1","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 J.","year":"2009","unstructured":"J. Simpson , K. Wong , S. Jackman , J. Schein , S. Jones , and I. Birol . Abyss: a parallel assembler for short read sequence data . Genome research , 19 ( 6 ): 1117 - 1123 , 2009 . J. Simpson, K. Wong, S. Jackman, J. Schein, S. Jones, and I. Birol. Abyss: a parallel assembler for short read sequence data. Genome research, 19(6):1117-1123, 2009.","journal-title":"Genome research"},{"key":"e_1_2_1_24_1","volume-title":"External duplicate deletion with large main memories","author":"Teuhola J.","year":"1993","unstructured":"J. Teuhola . External duplicate deletion with large main memories . 1993 . J. Teuhola. External duplicate deletion with large main memories. 1993."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/102868.102872"},{"issue":"5","key":"e_1_2_1_26_1","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 D.","year":"2008","unstructured":"D. Zerbino and E. Birney . Velvet: algorithms for de novo short read assembly using de bruijn graphs . Genome research , 18 ( 5 ): 821 - 829 , 2008 . D. Zerbino and E. Birney. Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome research, 18(5):821-829, 2008.","journal-title":"Genome research"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2535569.2448951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T23:56:32Z","timestamp":1690415792000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2535569.2448951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.14778\/2535569.2448951"],"URL":"https:\/\/doi.org\/10.14778\/2535569.2448951","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}