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...
Autores principales: | , , |
---|---|
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 |