Sequences and the de Bruijn Graph
Properties, Constructions, and Applications
- 1st Edition - February 29, 2024
- Author: Tuvi Etzion
- Language: English
- Paperback ISBN:9 7 8 - 0 - 4 4 3 - 1 3 5 1 7 - 0
- eBook ISBN:9 7 8 - 0 - 4 4 3 - 1 3 5 1 8 - 7
Sequences and the de Bruijn Graph: Properties, Constructions, and Applications explores the foundations of theoretical mathematical concepts and their important applicati… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteSequences and the de Bruijn Graph: Properties, Constructions, and Applications explores the foundations of theoretical mathematical concepts and their 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 properties, constructions, and interconnection networks. This book is suitable for researchers, graduate students, professors, and professionals working in the fields of applied mathematics, electrical engineering, computer science, and bioinformatics.
The de Bruijn graph was defined in 1946 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.
- Investigates computational and engineering applications associated with the de Bruijn graph, its sequences, and their generalization
- Explores one-dimensional and two-dimensional sequences with special properties and their various properties and applications
- Introduces the rich structure of the de Bruijn graph and its sequences, in both mathematical theory and its applications to computing and engineering problems
Researchers, graduate students, professors, and professionals working in the fields of applied mathematics, electrical engineering, computer science, and bioinformatics
- Cover image
- Title page
- Table of Contents
- Copyright
- Dedication
- Preface
- Chapter 1: Introduction
- Abstract
- 1.1. Some concepts in finite fields and number theory
- 1.2. Codes, graphs, and sequences
- 1.3. The de Bruijn graph and feedback shift registers
- 1.4. Overview of the chapters
- 1.5. Notes
- References
- Chapter 2: LFSR sequences
- Abstract
- 2.1. Sequence length and polynomial representation
- 2.2. Maximum length linear shift-register sequences
- 2.3. Powers of irreducible polynomials
- 2.4. Patterns with distinct differences
- 2.5. Notes
- References
- Chapter 3: Cycles and the nonlinear theory
- Abstract
- 3.1. Cycles from feedback shift registers
- 3.2. Enumeration methods for polynomials and cycles
- 3.3. Maximum number of cycles in a state diagram
- 3.4. Notes
- References
- Chapter 4: Constructions of full cycles
- Abstract
- 4.1. Enumeration of all Eulerian cycles
- 4.2. The D-morphism and recursive constructions
- 4.3. Merging cycles of large factors
- 4.4. Notes
- References
- Chapter 5: Linear complexity of sequences
- Abstract
- 5.1. Binary sequences whose length is 2n
- 5.2. Complexity of binary de Bruijn sequences
- 5.3. Sequences over pm whose length is pn, p prime
- 5.4. Complexity of non-binary de Bruijn sequences
- 5.5. Notes
- References
- Chapter 6: Classification of sequences
- Abstract
- 6.1. Classification of sequences with length 2n−1
- 6.2. Classification of de Bruijn sequences
- 6.3. Classification of balanced sequences
- 6.4. The depth of a word
- 6.5. Notes
- References
- Chapter 7: One-dimensional applications
- Abstract
- 7.1. Stream ciphers
- 7.2. VLSI testing
- 7.3. Single-track Gray codes
- 7.4. Rotating-table games
- 7.5. Notes
- References
- Chapter 8: DNA sequences and DNA codes
- Abstract
- 8.1. The genome assembly
- 8.2. DNA storage codes
- 8.3. Constant-weight de Bruijn sequences
- 8.4. Reconstruction of a sequence from subsequences
- 8.5. Synchronization codes
- 8.6. Notes
- References
- Chapter 9: Two-dimensional arrays
- Abstract
- 9.1. Graph representations of perfect maps
- 9.2. Constructions by merging cycles
- 9.3. Pseudo-random arrays
- 9.4. Recursive constructions for perfect maps
- 9.5. Two-dimensional arrays with distinct differences
- 9.6. Notes
- References
- Chapter 10: Two-dimensional applications
- Abstract
- 10.1. Robust self-location two-dimensional patterns
- 10.2. Key predistribution for sensor networks
- 10.3. Folding of one-dimensional sequences
- 10.4. Notes
- References
- Chapter 11: Unique path property graphs
- Abstract
- 11.1. Basic properties of UPP graphs
- 11.2. Constructions for UPP graphs
- 11.3. Cycles and factors in UPP graphs
- 11.4. Notes
- References
- Chapter 12: Interconnection networks
- Abstract
- 12.1. The shuffle-exchange network
- 12.2. Multistage interconnection networks
- 12.3. Multistage permutation networks
- 12.4. Layouts
- 12.5. Notes
- References
- Index
- No. of pages: 482
- Language: English
- Edition: 1
- Published: February 29, 2024
- Imprint: Academic Press
- Paperback ISBN: 9780443135170
- eBook ISBN: 9780443135187
TE
Tuvi Etzion
Tuvi Etzion is a professor of computer science at Technion – Israel Institute of Technology in Haifa, Israel. He has published more than 130 papers in leading scientific journals and IEEE fellow. His research interests include applications of discrete mathematics to problems in computer science and information theory, coding theory, digital sequences in coding and communication, network coding, coding for memories, and combinatorial designs.
Affiliations and expertise
Professor, Technion – Israel Institute of Technology, Haifa, IsraelRead Sequences and the de Bruijn Graph on ScienceDirect