{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T06:06:38Z","timestamp":1772690798633,"version":"3.50.1"},"reference-count":9,"publisher":"Public Library of Science (PLoS)","issue":"5","license":[{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Many students are taught about genome assembly using the dichotomy between the complexity of finding Eulerian and Hamiltonian cycles (easy versus hard, respectively). This dichotomy is sometimes used to motivate the use of de Bruijn graphs in practice. In this paper, we explain that while de Bruijn graphs have indeed been very useful, the reason has nothing to do with the complexity of the Hamiltonian and Eulerian cycle problems. We give 2 arguments. The first is that a genome reconstruction is never unique and hence an algorithm for finding Eulerian or Hamiltonian cycles is not part of any assembly algorithm used in practice. The second is that even if an arbitrary genome reconstruction was desired, one could do so in linear time in both the Eulerian and Hamiltonian paradigms.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1008928","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T17:26:26Z","timestamp":1621531586000},"page":"e1008928","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":8,"title":["What do Eulerian and Hamiltonian cycles have to do with genome assembly?"],"prefix":"10.1371","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3143-594X","authenticated-orcid":true,"given":"Paul","family":"Medvedev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9617-5304","authenticated-orcid":true,"given":"Mihai","family":"Pop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"340","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"issue":"6","key":"pcbi.1008928.ref001","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1089\/cmb.2016.0141","article-title":"Safe and complete contig assembly through omnitigs","volume":"24","author":"AI Tomescu","year":"2017","journal-title":"J Comput Biol"},{"issue":"7","key":"pcbi.1008928.ref002","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1089\/cmb.2009.0005","article-title":"Parametric complexity of sequence assembly: theory and applications to next generation sequencing","volume":"16","author":"N Nagarajan","year":"2009","journal-title":"J Comput Biol"},{"issue":"4","key":"pcbi.1008928.ref003","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1093\/bib\/bby003","article-title":"Modeling biological problems in computer science: a case study in genome assembly","volume":"20","author":"P Medvedev","year":"2019","journal-title":"Brief Bioinformatics"},{"key":"pcbi.1008928.ref004","first-page":"289","volume-title":"In: International Workshop on Algorithms in Bioinformatics","author":"P Medvedev","year":"2007"},{"issue":"1","key":"pcbi.1008928.ref005","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1471-2105-11-21","article-title":"Assembly complexity of prokaryotic genomes using short reads","volume":"11","author":"C Kingsford","year":"2010","journal-title":"BMC Bioinformatics"},{"issue":"S5","key":"pcbi.1008928.ref006","doi-asserted-by":"crossref","first-page":"S18","DOI":"10.1186\/1471-2105-14-S5-S18","article-title":"Optimal assembly for high throughput shotgun sequencing","volume":"14","author":"G Bresler","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"pcbi.1008928.ref007","first-page":"758","article-title":"A Combinatorial Problem","volume":"49","author":"N De Bruijn","year":"1946","journal-title":"Koninklijke Nederlandse Akademie V Wetenschappen"},{"issue":"3","key":"pcbi.1008928.ref008","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1112\/jlms\/s1-21.3.167","article-title":"Normal recurring decimals","volume":"21","author":"IJ Good","year":"1946","journal-title":"J Lond Math Soc"},{"key":"pcbi.1008928.ref009","volume-title":"Digraphs: theory, algorithms and applications","author":"J Bang-Jensen","year":"2008"}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T17:26:33Z","timestamp":1621531593000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008928"}},"subtitle":[],"editor":[{"given":"Francis","family":"Ouellette","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,5,20]]},"references-count":9,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5,20]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1008928","relation":{},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,20]]}}}