Cargando…

What do Eulerian and Hamiltonian cycles have to do with genome assembly?

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Medvedev, Paul, Pop, Mihai
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8136698/
https://www.ncbi.nlm.nih.gov/pubmed/34014915
http://dx.doi.org/10.1371/journal.pcbi.1008928
_version_ 1783695479413932032
author Medvedev, Paul
Pop, Mihai
author_facet Medvedev, Paul
Pop, Mihai
author_sort Medvedev, Paul
collection PubMed
description 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.
format Online
Article
Text
id pubmed-8136698
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-81366982021-06-02 What do Eulerian and Hamiltonian cycles have to do with genome assembly? Medvedev, Paul Pop, Mihai PLoS Comput Biol Education 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. Public Library of Science 2021-05-20 /pmc/articles/PMC8136698/ /pubmed/34014915 http://dx.doi.org/10.1371/journal.pcbi.1008928 Text en © 2021 Medvedev, Pop https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Education
Medvedev, Paul
Pop, Mihai
What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title_full What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title_fullStr What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title_full_unstemmed What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title_short What do Eulerian and Hamiltonian cycles have to do with genome assembly?
title_sort what do eulerian and hamiltonian cycles have to do with genome assembly?
topic Education
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8136698/
https://www.ncbi.nlm.nih.gov/pubmed/34014915
http://dx.doi.org/10.1371/journal.pcbi.1008928
work_keys_str_mv AT medvedevpaul whatdoeulerianandhamiltoniancycleshavetodowithgenomeassembly
AT popmihai whatdoeulerianandhamiltoniancycleshavetodowithgenomeassembly