Cargando…

What is the difference between the breakpoint graph and the de Bruijn graph?

The breakpoint graph and the de Bruijn graph are two key data structures in the studies of genome rearrangements and genome assembly. However, the classical breakpoint graphs are defined on two genomes (represented as sequences of synteny blocks), while the classical de Bruijn graphs are defined on...

Descripción completa

Detalles Bibliográficos
Autores principales: Lin, Yu, Nurk, Sergey, Pevzner, Pavel A
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4240671/
https://www.ncbi.nlm.nih.gov/pubmed/25572416
http://dx.doi.org/10.1186/1471-2164-15-S6-S6
_version_ 1782345752619515904
author Lin, Yu
Nurk, Sergey
Pevzner, Pavel A
author_facet Lin, Yu
Nurk, Sergey
Pevzner, Pavel A
author_sort Lin, Yu
collection PubMed
description The breakpoint graph and the de Bruijn graph are two key data structures in the studies of genome rearrangements and genome assembly. However, the classical breakpoint graphs are defined on two genomes (represented as sequences of synteny blocks), while the classical de Bruijn graphs are defined on a single genome (represented as DNA strings). Thus, the connection between these two graph models is not explicit. We generalize the notions of both the breakpoint graph and the de Bruijn graph, and make it transparent that the breakpoint graph and the de Bruijn graph are mathematically equivalent. The explicit description of the connection between these important data structures provides a bridge between two previously separated bioinformatics communities studying genome rearrangements and genome assembly.
format Online
Article
Text
id pubmed-4240671
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-42406712014-11-25 What is the difference between the breakpoint graph and the de Bruijn graph? Lin, Yu Nurk, Sergey Pevzner, Pavel A BMC Genomics Research The breakpoint graph and the de Bruijn graph are two key data structures in the studies of genome rearrangements and genome assembly. However, the classical breakpoint graphs are defined on two genomes (represented as sequences of synteny blocks), while the classical de Bruijn graphs are defined on a single genome (represented as DNA strings). Thus, the connection between these two graph models is not explicit. We generalize the notions of both the breakpoint graph and the de Bruijn graph, and make it transparent that the breakpoint graph and the de Bruijn graph are mathematically equivalent. The explicit description of the connection between these important data structures provides a bridge between two previously separated bioinformatics communities studying genome rearrangements and genome assembly. BioMed Central 2014-10-17 /pmc/articles/PMC4240671/ /pubmed/25572416 http://dx.doi.org/10.1186/1471-2164-15-S6-S6 Text en Copyright © 2014 Lin et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/4.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Research
Lin, Yu
Nurk, Sergey
Pevzner, Pavel A
What is the difference between the breakpoint graph and the de Bruijn graph?
title What is the difference between the breakpoint graph and the de Bruijn graph?
title_full What is the difference between the breakpoint graph and the de Bruijn graph?
title_fullStr What is the difference between the breakpoint graph and the de Bruijn graph?
title_full_unstemmed What is the difference between the breakpoint graph and the de Bruijn graph?
title_short What is the difference between the breakpoint graph and the de Bruijn graph?
title_sort what is the difference between the breakpoint graph and the de bruijn graph?
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4240671/
https://www.ncbi.nlm.nih.gov/pubmed/25572416
http://dx.doi.org/10.1186/1471-2164-15-S6-S6
work_keys_str_mv AT linyu whatisthedifferencebetweenthebreakpointgraphandthedebruijngraph
AT nurksergey whatisthedifferencebetweenthebreakpointgraphandthedebruijngraph
AT pevznerpavela whatisthedifferencebetweenthebreakpointgraphandthedebruijngraph