🧬 De Bruijn Foundations
🎯 What are De Bruijn Sequences?
De Bruijn sequences are cyclic sequences of length k^n that contain every possible subsequence of length n exactly once. Named after Nicolaas Govert de Bruijn (1946).
Core Concepts
Order n: Length of subsequences. Alphabet size k: Number of symbols. Length: k^n unique subsequences. Cyclic: Last n-1 characters wrap to first.
# Example: Binary De Bruijn sequence of order 3
# Contains all 8 binary strings of length 3
de_bruijn_3 = "00010111"
# Substrings: 000, 001, 010, 101, 011, 111, 110, 100
# Cyclic: last 2 digits wrap to first🔢 Sequence Definition
🎯 Formal Definition
A De Bruijn sequence B(k,n) is a cyclic sequence of length k^n over an alphabet of size k, such that every length-n string appears exactly once as a contiguous substring.
Notation & Examples
B(2,2): 0011 contains 00,01,11,10. B(2,3): 00010111. B(3,2): 001021122 (contains all 9 2-digit base-3 strings).
def is_de_bruijn(sequence, k, n):
"""Check if sequence is a valid De Bruijn sequence"""
if len(sequence) != k**n:
return False
# Check all substrings of length n are unique
substrings = set()
for i in range(len(sequence)):
substr = sequence[i:i+n]
if len(substr) < n:
# Wrap around
substr = sequence[i:] + sequence[:n-len(substr)]
if substr in substrings:
return False
substrings.add(substr)
return len(substrings) == k**n📊 De Bruijn Graphs
🎯 Graph Representation
De Bruijn graphs have vertices as (n-1)-length strings. Edges represent n-length strings. The De Bruijn sequence is an Eulerian cycle.
Graph Construction
Vertices: All strings of length n-1. Edges: From prefix to suffix of each length-n string. Degree: k incoming, k outgoing.
def build_de_bruijn_graph(k, n):
"""Build De Bruijn graph for alphabet size k and order n"""
vertices = [''.join(p) for p in product(range(k), repeat=n-1)]
edges = {}
for v in vertices:
for symbol in range(k):
edge = v + str(symbol)
target = edge[1:]
edges[edge] = target
return vertices, edges🔄 Eulerian Cycles
🎯 Eulerian Cycle Existence
De Bruijn graphs are Eulerian: all vertices have equal in-degree and out-degree (k). The De Bruijn sequence corresponds to an Eulerian cycle.
Eulerian Cycle Algorithm
Hierholzer's algorithm: Find Eulerian cycle in directed graph. Guaranteed: All vertices have equal in/out degree. Complexity: O(k^n).
def hierholzer(graph):
"""Find Eulerian cycle using Hierholzer's algorithm"""
stack = []
cycle = []
current = next(iter(graph))
stack.append(current)
while stack:
if graph[current]:
stack.append(current)
current = graph[current].pop()
else:
cycle.append(current)
current = stack.pop()
return list(reversed(cycle))🧩 Hamiltonian Paths
🎯 Hamiltonian View
De Bruijn sequences correspond to Hamiltonian paths in De Bruijn graphs (visiting each vertex exactly once).
Hamiltonian vs Eulerian
Hamiltonian: Visit each vertex exactly once. Eulerian: Traverse each edge exactly once. Duality: De Bruijn graphs are line graphs.
def hamiltonian_to_eulerian(hamiltonian_path):
"""Convert Hamiltonian path to Eulerian cycle"""
# Hamiltonian path gives ordering of vertices
# Convert to edge sequence
edges = []
for i in range(len(hamiltonian_path)-1):
edges.append(hamiltonian_path[i] + hamiltonian_path[i+1][-1])
return edges🔧 Construction Algorithms
🎯 Building De Bruijn Sequences
Multiple algorithms exist: Hierholzer's (Eulerian), FKM (Ford-Fulkerson), prefer-one, and Lyndon word concatenation.
Algorithm Comparison
Eulerian: Build graph, find Eulerian cycle. Prefer-one: Greedy algorithm. Lyndon: Concatenate Lyndon words.
def de_bruijn_eulerian(k, n):
"""Construct De Bruijn sequence using Eulerian cycle"""
graph = build_de_bruijn_graph(k, n)
cycle = hierholzer(graph)
# Extract sequence from edges
sequence = cycle[0]
for edge in cycle[1:]:
sequence += edge[-1]
return sequence📈 Lyndon Words
🎯 Lyndon Word Concatenation
De Bruijn sequences can be constructed by concatenating Lyndon words (primitive, lexicographically minimal among rotations).
Lyndon Properties
Primitive: Not a power of a smaller word. Minimal: Lexicographically smallest rotation. FKM: Ford-Fulkerson algorithm for Lyndon words.
def lyndon_words(k, n):
"""Generate Lyndon words of length <= n over alphabet size k"""
words = []
def gen(word):
if len(word) == n:
return
for i in range(k):
new_word = word + str(i)
# Check if primitive and minimal
if is_lyndon(new_word):
words.append(new_word)
gen(new_word)
gen('')
return words
def de_bruijn_lyndon(k, n):
"""Construct De Bruijn using Lyndon words"""
words = sorted(lyndon_words(k, n))
return ''.join(words)⚡ Prefer-One Algorithm
🎯 Greedy Construction
The prefer-one algorithm greedily chooses the smallest possible next symbol, producing De Bruijn sequences efficiently.
Algorithm Steps
Start: n zeros. Step: Try adding 1, if not visited; else 0. Stop: When length reaches k^n.
def prefer_one(k, n):
"""Prefer-one algorithm for De Bruijn sequences"""
sequence = [0] * n # Start with n zeros
visited = set()
visited.add(tuple(sequence))
while len(sequence) < k**n:
# Try to append 1 first
for bit in range(k-1, -1, -1):
candidate = tuple(sequence[-(n-1):] + [bit])
if candidate not in visited:
sequence.append(bit)
visited.add(candidate)
break
else:
break
return sequence📐 Key Properties
🎯 Mathematical Properties
De Bruijn sequences have fascinating properties: they are optimal, have numerous applications, and exhibit fractal-like structure.
Key Theorems
Existence: A De Bruijn sequence exists for all k,n. Count: (k!)^(k^(n-1)) / k^n distinct sequences. Combinatorial: Related to necklaces and Lyndon words.
def count_de_bruijn(k, n):
"""Count number of distinct De Bruijn sequences"""
import math
# Formula: (k!)^(k^(n-1)) / k^n
numerator = math.factorial(k) ** (k ** (n-1))
denominator = k ** n
return numerator // denominator🧬 Genomics Applications
🎯 DNA Sequencing
De Bruijn graphs are fundamental to genome assembly, where short DNA reads are assembled into longer sequences.
Genome Assembly Pipeline
Reads: Short DNA fragments. Graph: Build De Bruijn graph of k-mers. Assembly: Find Hamiltonian/Eulerian paths.
class GenomeAssembler:
def __init__(self, k):
self.k = k
self.graph = {}
def add_read(self, read):
"""Add a DNA read to the De Bruijn graph"""
for i in range(len(read) - self.k + 1):
kmer = read[i:i+self.k]
prefix = kmer[:-1]
suffix = kmer[1:]
if prefix not in self.graph:
self.graph[prefix] = []
self.graph[prefix].append(suffix)
def assemble(self):
"""Assemble genome from De Bruijn graph"""
return find_eulerian_path(self.graph)🔒 Cryptography
🎯 Cryptographic Applications
De Bruijn sequences are used in cryptography for generating pseudo-random sequences, covering codes, and cipher design.
Crypto Properties
Randomness: De Bruijn sequences have balanced properties. Covering codes: Minimum distance properties. Stream ciphers: Sequence generation.
class DeBruijnCipher:
def __init__(self, k, n):
self.sequence = de_bruijn_prefer_one(k, n)
self.position = 0
def encrypt(self, plaintext):
"""XOR with De Bruijn sequence"""
ciphertext = []
for char in plaintext:
key_bit = self.sequence[self.position % len(self.sequence)]
ciphertext.append(char ^ key_bit)
self.position += 1
return ciphertext🌐 Network Design
🎯 Network Topologies
De Bruijn graphs are used in network design for interconnection networks, providing good diameter and degree properties.
Network Properties
Diameter: O(log_k N). Degree: 2k. Fault tolerance: High connectivity.
class DeBruijnNetwork:
def __init__(self, k, n):
self.nodes = [''.join(p) for p in product(range(k), repeat=n)]
self.edges = {}
for node in self.nodes:
for symbol in range(k):
self.edges[node] = node[1:] + str(symbol)
def route(self, source, target):
"""Find shortest path in De Bruijn network"""
# Greedy routing
path = [source]
current = source
while current != target:
# Find next node that maximizes overlap with target
next_node = self.edges[current]
# Simple: just follow edge
path.append(next_node)
current = next_node
return path⚡ Advanced Algorithms
🎯 State-of-the-Art Methods
Advanced algorithms include parallel construction, subsequence finding, and applications in bioinformatics.
Modern Techniques
Parallel: Divide and conquer for large k. GPU: Accelerated graph traversal. Streaming: Online sequence generation.
def parallel_de_bruijn(k, n, num_threads):
"""Parallel construction of De Bruijn sequence"""
# Split work by prefixes
prefixes = [''.join(p) for p in product(range(k), repeat=n-2)]
results = []
with ThreadPoolExecutor(max_workers=num_threads) as executor:
futures = []
for prefix in prefixes:
futures.append(executor.submit(build_subsequence, prefix, k, n))
for future in futures:
results.extend(future.result())
return merge_subsequences(results)🔬 Research Frontiers
🎯 Open Problems
Current research includes higher-dimensional De Bruijn sequences, generalizations to non-uniform alphabets, and applications in quantum computing.
Research Directions
Multi-dimensional: 2D and 3D De Bruijn sequences. Weighted: Non-uniform symbol probabilities. Quantum: Quantum algorithms for generation.
def multi_dimensional_de_bruijn(dimensions):
"""Construct multi-dimensional De Bruijn sequences"""
# Future research: generalize to d dimensions
# Currently area of active research
pass