de Bruijn graph

E239167

combinatorial structure directed graph mathematical concept

A de Bruijn graph is a directed graph structure that compactly represents overlaps between sequences of symbols, widely used in combinatorics, coding theory, and genome assembly algorithms.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (2)

Label	Occurrences
de Bruijn graph canonical	3
de Bruijn graphs	1

Statements (47)

Predicate	Object
instanceOf	combinatorial structure ⓘ directed graph ⓘ mathematical concept ⓘ
advantage	enables linear-time traversal for assembly under ideal conditions ⓘ memory-efficient representation of sequence overlaps ⓘ
alphabet	finite alphabet of symbols ⓘ
applicationDomain	metagenomic assembly ⓘ next-generation sequencing ⓘ short-read assembly ⓘ
challenge	graph simplification and compaction ⓘ handling sequencing errors ⓘ resolving repeats ⓘ
coloredVariantUsedFor	representing multiple genomes or samples ⓘ
commonAlgorithmicUse	finding Eulerian paths to reconstruct sequences ⓘ
compactedVariantUsedFor	reducing number of vertices and edges ⓘ
edgeDirectionMeaning	extension of a (k−1)-mer by one symbol ⓘ
field	bioinformatics ⓘ coding theory ⓘ combinatorics ⓘ genome assembly ⓘ graph theory ⓘ
hasProperty	can be very large for genomic data ⓘ compact representation of overlaps ⓘ directed ⓘ edges represent overlaps ⓘ often constructed from k-mers ⓘ supports Eulerian path traversal ⓘ vertices represent substrings ⓘ
hasVariant	colored de Bruijn graph ⓘ compacted de Bruijn graph ⓘ weighted de Bruijn graph ⓘ
historicalContext	introduced in the study of de Bruijn sequences ⓘ
namedAfter	N. G. de Bruijn ⓘ surface form: Nicolaas Govert de Bruijn
relatedTo	Eulerian path ⓘ assembly graph ⓘ de Bruijn sequence ⓘ k-mer ⓘ overlap graph ⓘ string graph ⓘ
typicalEdgeDefinition	k-mer whose prefix and suffix are vertices ⓘ
typicalVertexDefinition	(k−1)-mer over a given alphabet ⓘ
usedFor	design of de Bruijn sequences ⓘ error correction in sequencing data ⓘ genome assembly algorithms ⓘ modeling k-mer overlaps ⓘ representing overlaps between sequences of symbols ⓘ sequence assembly ⓘ

Referenced by (4)

Full triples — surface form annotated when it differs from this entity's canonical label.

N. G. de Bruijn → notableWork → de Bruijn graph ⓘ

de Bruijn sequence → relatedTo → de Bruijn graph ⓘ

de Bruijn–van Aardenne–Ehrenfest theorem → appliesTo → de Bruijn graph ⓘ

this entity surface form: de Bruijn graphs

de Bruijn–van Aardenne–Ehrenfest theorem → relatedTo → de Bruijn graph ⓘ