{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/24291"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/24291","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scaling short read de novo DNA sequence assembly to gigabase genomes","abstract":"The recent advent of massively parallel sequencing technologies has drastically reduced the cost of sequencing, sparking a revolution in whole genome de novo sequencing. However, these new technologies sample much shorter segments of DNA, called short reads, than conventional but more costly long read sequencing technologies, and suffer from higher and more varied error rates. Modern genome assembly tools compensate for these shortcomings by using de Bruijn graph based assembly techniques; however, for large genomes, the physical memory required to efficiently build and manipulate the de Bruijn graph generally far exceeds that which is available on modern commodity workstations. This dissertation develops novel out-of-core algorithms that permit conservative assembly of the de Bruijn graph using one to three orders of magnitude less memory than is required by the naïve approach. These algorithms are implemented in an open source genome assembly tool that replaces the front-end assembly process, which can connect to existing back-end tools in a manner that attempts to decouple the phases that have performance concerns but simple heuristics, from those that have complex heuristics but relatively straightforward implementations, in a way that allows each to be developed by domain experts.","abstract_html":"The recent advent of massively parallel sequencing technologies has drastically reduced the cost of sequencing, sparking a revolution in whole genome de novo sequencing. However, these new technologies sample much shorter segments of DNA, called short reads, than conventional but more costly long read sequencing technologies, and suffer from higher and more varied error rates. Modern genome assembly tools compensate for these shortcomings by using de Bruijn graph based assembly techniques; however, for large genomes, the physical memory required to efficiently build and manipulate the de Bruijn graph generally far exceeds that which is available on modern commodity workstations. This dissertation develops novel out-of-core algorithms that permit conservative assembly of the de Bruijn graph using one to three orders of magnitude less memory than is required by the naïve approach. These algorithms are implemented in an open source genome assembly tool that replaces the front-end assembly process, which can connect to existing back-end tools in a manner that attempts to decouple the phases that have performance concerns but simple heuristics, from those that have complex heuristics but relatively straightforward implementations, in a way that allows each to be developed by domain experts.","abstract_has_math":false,"creators":["Cook, Jeffrey J."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Zilles, Craig","Hudson, Matthew E.","Lumetta, Steven S.","Patel, Sanjay J.","Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-25T15:03:13Z","date_published":"2011-05-25T15:03:13Z","updated_at":"2026-07-22T22:25:23Z","subjects":["de novo sequence assembly","de Bruijn graph","Eulerian assembly","gigabase genome assembly","Deoxyribonucleic Acid (DNA)","short reads","massively parallel sequencing"],"languages":["en"],"rights":["Copyright 2011 Jeffrey J. Cook"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/24291","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Zilles, Craig","Hudson, Matthew E.","Lumetta, Steven S.","Patel, Sanjay J.","Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Cook, Jeffrey J."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-25T15:03:13Z","2011-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["de novo sequence assembly","de Bruijn graph","Eulerian assembly","gigabase genome assembly","Deoxyribonucleic Acid (DNA)","short reads","massively parallel sequencing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Jeffrey J. Cook"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/24291"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The recent advent of massively parallel sequencing technologies has drastically reduced the cost of sequencing, sparking a revolution in whole genome de novo sequencing. However, these new technologies sample much shorter segments of DNA, called short reads, than conventional but more costly long read sequencing technologies, and suffer from higher and more varied error rates. Modern genome assembly tools compensate for these shortcomings by using de Bruijn graph based assembly techniques; however, for large genomes, the physical memory required to efficiently build and manipulate the de Bruijn graph generally far exceeds that which is available on modern commodity workstations. This dissertation develops novel out-of-core algorithms that permit conservative assembly of the de Bruijn graph using one to three orders of magnitude less memory than is required by the naïve approach. These algorithms are implemented in an open source genome assembly tool that replaces the front-end assembly process, which can connect to existing back-end tools in a manner that attempts to decouple the phases that have performance concerns but simple heuristics, from those that have complex heuristics but relatively straightforward implementations, in a way that allows each to be developed by domain experts.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-18T13:40:35Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Cook_Jeffrey.pdf: 2855851 bytes, checksum: 35e1fbf70c006ea444bb87dbe1bea15c (MD5)","Made available in DSpace on 2011-05-25T15:03:13Z (GMT). No. of bitstreams: 2 Cook_Jeffrey.pdf: 2855851 bytes, checksum: 35e1fbf70c006ea444bb87dbe1bea15c (MD5) license.txt: 4060 bytes, checksum: 3fb8c5049bdd0ace682370f2a0befec7 (MD5)"]},{"key":"dc:title","label":"Title","values":["Scaling short read de novo DNA sequence assembly to gigabase genomes"]}]}],"canonical_facts":{"dc:contributor":["Zilles, Craig","Hudson, Matthew E.","Lumetta, Steven S.","Patel, Sanjay J.","Wong, Martin D.F."],"dc:creator":["Cook, Jeffrey J."],"dc:date":["2011-05-25T15:03:13Z","2011-05"],"dc:description":["The recent advent of massively parallel sequencing technologies has drastically reduced the cost of sequencing, sparking a revolution in whole genome de novo sequencing. However, these new technologies sample much shorter segments of DNA, called short reads, than conventional but more costly long read sequencing technologies, and suffer from higher and more varied error rates. Modern genome assembly tools compensate for these shortcomings by using de Bruijn graph based assembly techniques; however, for large genomes, the physical memory required to efficiently build and manipulate the de Bruijn graph generally far exceeds that which is available on modern commodity workstations. This dissertation develops novel out-of-core algorithms that permit conservative assembly of the de Bruijn graph using one to three orders of magnitude less memory than is required by the naïve approach. These algorithms are implemented in an open source genome assembly tool that replaces the front-end assembly process, which can connect to existing back-end tools in a manner that attempts to decouple the phases that have performance concerns but simple heuristics, from those that have complex heuristics but relatively straightforward implementations, in a way that allows each to be developed by domain experts.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-04-18T13:40:35Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Cook_Jeffrey.pdf: 2855851 bytes, checksum: 35e1fbf70c006ea444bb87dbe1bea15c (MD5)","Made available in DSpace on 2011-05-25T15:03:13Z (GMT). No. of bitstreams: 2 Cook_Jeffrey.pdf: 2855851 bytes, checksum: 35e1fbf70c006ea444bb87dbe1bea15c (MD5) license.txt: 4060 bytes, checksum: 3fb8c5049bdd0ace682370f2a0befec7 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/24291"],"dc:language":["en"],"dc:rights":["Copyright 2011 Jeffrey J. Cook"],"dc:subject":["de novo sequence assembly","de Bruijn graph","Eulerian assembly","gigabase genome assembly","Deoxyribonucleic Acid (DNA)","short reads","massively parallel sequencing"],"dc:title":["Scaling short read de novo DNA sequence assembly to gigabase genomes"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:23Z"}