What is the difference between the breakpoint graph and the de Bruijn graph?
Date
2014
Authors
Lin, Yu
Nurk, Sergey
Pevzner, Pavel A.
Journal Title
Journal ISSN
Volume Title
Publisher
BioMed Central
Abstract
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.
Description
Keywords
Citation
Collections
Source
BMC Genomics
Type
Journal article
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description