bioRxiv (Cold Spring Harbor Laboratory) · 2017 · 50 citations · 13 references
ComputingBioinformaticsBiologyComputational BiologyData StructuresGenomic Data AnalysisColor RepresentationComputational GenomicsGraph TheoryBoss FeaturesColored De Bruijn GraphsComputational Biology ModelsEquivalence Relation RepresentationGraph-based Genome RepresentationK-mer Graph ConstructionSuccinct De Bruijn Graphs
Abstract The colored de Bruijn graph— a variant of the de Bruijn graph which associates each edge (i.e., k-mer) with some set of colors — is an increasingly important combinatorial structure in computational biology. Iqbal et al. demonstrated the utility of this structure for representing and assembling a collection (pop-ulation) of genomes, and showed how it can be used to accurately detect genetic variants. Muggli et al. introduced VARI, a representation of the colored de Bruijn graph that adopts the BOSS representation for the de Bruijn graph topology and achieves considerable savings in space over Cortex , albeit with some sacrifice in speed. The memory-efficient representation of VARI allows the colored de Bruijn graph to be constructed and analyzed for large datasets, beyond what is possible with Cortex . In this paper, we introduce Rainbowfish, a succinct representation of the color information of the colored de Bruijn graph that reduces the space usage even further. Our representation also uses BOSS to represent the de Bruijn graph, but decomposes the color sets based on an equivalence relation and exploits the inherent skewness in the distribution of these color sets. The Rainbowfish representation is compressed based on the 0th-order entropy of the color sets, which can lead to a significant reduction in the space required to store the relevant information for each edge. In practice, Rainbowfish achieves up to a 20 × improvement in space over VARI. Rainbowfish is written in C++11 and is available at https://github.com/COMBINE-lab/rainbowfish .
13
GENCODE: The reference human genome annotation for The ENCODE Project
Jennifer Harrow, Adam Frankish, José M. González et al. · Genome Research · 2012 · 5K citations · Full text
The B73 Maize Genome: Complexity, Diversity, and Dynamics
Patrick S. Schnable, Doreen Ware, Robert S. Fulton et al. · Science · 2009 · 4.2K citations
De novo assembly and genotyping of variants using colored de Bruijn graphs
Zamin Iqbal, Mario Cáccamo, Isaac Turner et al. · Nature Genetics · 2012 · 716 citations