The de Bruijn graph was defined in 1949 to enumerate the number of closed sequences where each n-tuple appears exactly once as a window in a sequence. Through the years, the graph and its sequences have found numerous applications – in space technology, wireless communication, cryptography, parallel computation, genome assembly, DNA storage, and microbiome research, among others.
Sequences and the de Bruijn Graph: Properties, Constructions, and Applications explores the foundations of theoretical mathematical concepts and the important applications to computer science, electrical engineering, and bioinformatics. The book introduces the various concepts, ideas, and techniques associated with the use of the de Bruijn Graph, providing comprehensive coverage of sequence classification, one-dimensional and two-dimensional applications, graphs, interconnected networks, layouts, and embedded systems. Researchers, graduate students, professors, and professionals working in the fields of applied mathematics, electrical engineering, computer science and bioinformatics will find this book useful.
1. Chapter 1 : Introduction: Preliminaries, de Bruijn graph, shift registers - p. Page xii 2. Chapter 2 : LFSR sequences: Polynomials, M-sequences, cycles, difference sets - p. Page 50 3. Chapter 3 : Cycles and the nonlinear theory: Necklaces, self-dual sequences, enumeration - p. Page 85 4. Chapter 4 : Constructions of full cycles: Full cycles, enumeration, D-morphism, algorithms - p. Page 117 5. Chapter 5 : Linear complexity of sequences: Algorithms, complexity of de Bruijn sequences - p. Page 149 6. Chapter 6 : Classification of sequences: Balanced sequences, the depth of a sequence - p. Page 185 7. Chapter 7 : One-dimensional applications: Cryptography, verification, Gray codes, and games - p. Page 216 8. Chapter 8 : DNA sequences and DNA codes: The genome assembly and DNA storage - p. Page 244 9. Chapter 9 : Two-dimensional arrays: Perfect maps and distinct differences arrays - p. Page 275 10. Chapter 10 : Two-dimensional applications: Self-location, secure sensor networks, folding - p. Page 321 11. Chapter 11 : Unique path property graphs: Properties, constructions, cycles, and factors - p. Page 363 12. Chapter 12 : Interconnection networks: Shuffle-exchange and permutation networks, layouts - p. Page 403 13. Index - p. Page 454
The de Bruijn graph was defined in 1949 to enumerate the number of closed sequences where each n-tuple appears exactly once as a window in a sequence. Through the years, the graph and its sequences have found numerous applications – in space technology, wireless communication, cryptography, parallel computation, genome assembly, DNA storage, and microbiome research, among others.
Sequences and the de Bruijn Graph: Properties, Constructions, and Applications explores the foundations of theoretical mathematical concepts and the important applications to computer science, electrical engineering, and bioinformatics. The book introduces the various concepts, ideas, and techniques associated with the use of the de Bruijn Graph, providing comprehensive coverage of sequence classification, one-dimensional and two-dimensional applications, graphs, interconnected networks, layouts, and embedded systems. Researchers, graduate students, professors, and professionals working in the fields of applied mathematics, electrical engineering, computer science and bioinformatics will find this book useful.
1. Chapter 1 : Introduction: Preliminaries, de Bruijn graph, shift registers - p. Page xii 2. Chapter 2 : LFSR sequences: Polynomials, M-sequences, cycles, difference sets - p. Page 50 3. Chapter 3 : Cycles and the nonlinear theory: Necklaces, self-dual sequences, enumeration - p. Page 85 4. Chapter 4 : Constructions of full cycles: Full cycles, enumeration, D-morphism, algorithms - p. Page 117 5. Chapter 5 : Linear complexity of sequences: Algorithms, complexity of de Bruijn sequences - p. Page 149 6. Chapter 6 : Classification of sequences: Balanced sequences, the depth of a sequence - p. Page 185 7. Chapter 7 : One-dimensional applications: Cryptography, verification, Gray codes, and games - p. Page 216 8. Chapter 8 : DNA sequences and DNA codes: The genome assembly and DNA storage - p. Page 244 9. Chapter 9 : Two-dimensional arrays: Perfect maps and distinct differences arrays - p. Page 275 10. Chapter 10 : Two-dimensional applications: Self-location, secure sensor networks, folding - p. Page 321 11. Chapter 11 : Unique path property graphs: Properties, constructions, cycles, and factors - p. Page 363 12. Chapter 12 : Interconnection networks: Shuffle-exchange and permutation networks, layouts - p. Page 403 13. Index - p. Page 454
