Abstract
Breakpoint graph analysis is a key algorithmic technique in studies of genome rearrangements. However, breakpoint graphs are defined only for genomes without duplicated genes, thus limiting their applications in rearrangement analysis. We discuss a connection between the breakpoint graphs and de Bruijn graphs that leads to a generalization of the notion of breakpoint graph for genomes with duplicated genes. We further use the generalized breakpoint graphs to study the Genome Halving Problem (first introduced and solved by Nadia El-Mabrouk and David Sankoff). The El-Mabrouk-Sankoff algorithm is rather complex, and, in this paper, we present an alternative approach that is based on generalized breakpoint graphs. The generalized breakpoint graphs make the El-Mabrouk-Sankoff result more transparent and promise to be useful in future studies of genome rearrangements.
Keywords
BreakpointDe Bruijn sequenceGenomeDe Bruijn graphCombinatoricsComputer scienceBiologyGeneticsMathematicsGeneChromosome
Affiliated Institutions
Related Publications
IDBA-UD: a <i>de novo</i> assembler for single-cell and metagenomic sequencing data with highly uneven depth
Abstract Motivation: Next-generation sequencing allows us to sequence reads from a microbial environment using single-cell sequencing or metagenomic sequencing technologies. How...
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs
We have developed a new set of algorithms, collectively called “Velvet,” to manipulate de Bruijn graphs for genomic sequence assembly. A de Bruijn graph is a compact representat...
A parallel graph decomposition algorithm for DNA sequencing with nanopores
Abstract Motivation: With the potential availability of nanopore devices that can sense the bases of translocating single-stranded DNA (ssDNA), it is likely that ‘reads’ of leng...
De novo assembly of human genomes with massively parallel short read sequencing
Next-generation massively parallel DNA sequencing technologies provide ultrahigh throughput at a substantially lower unit data cost; however, the data are very short read length...
Whole-Genome Sequencing and Assembly with High-Throughput, Short-Read Technologies
While recently developed short-read sequencing technologies may dramatically reduce the sequencing cost and eventually achieve the $1000 goal for re-sequencing, their limitation...
Publication Info
- Year
- 2007
- Type
- article
- Volume
- 4
- Issue
- 1
- Pages
- 98-107
- Citations
- 45
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
45
OpenAlex
Cite This
Max A. Alekseyev,
Pavel A. Pevzner
(2007).
Colored de Bruijn Graphs and the Genome Halving Problem.
IEEE/ACM Transactions on Computational Biology and Bioinformatics
, 4
(1)
, 98-107.
https://doi.org/10.1109/tcbb.2007.1002
Identifiers
- DOI
- 10.1109/tcbb.2007.1002