Title: The de Bruijn Graph and Its Sequences - the Graph Who Always Reinvent Itself

Speaker: Tuvi Etzion, Technion-Israel Institute of Technology

Date/Time: Sunday, 15th Sep ，10:00-11:00am 

Venue: 5206

Abstract:

The de Bruijn graph was defined in 1946 by Nicolaas Govert de Bruijn to count the number of closed sequences in which each binary n-tuple is contained exactly once ina window of length n. The graph and its sequences have found many applications indiverse areas during the last eighty years. Mathematical theory was developed throughout the years for mathematical interest. The first main application of the graph and its sequences was in space and wireless communication. Interconnection networks which were considered as a model for parallel computations used the graph as a framework for a network with processors transfer information. The human genome project which was started towards the end of the eighties ofthe 20th century also used paths of the de Bruijn graph for DNA sequencing which is part of the genomeassembly. It was considered in the nineties to built a Viterbi decoder for the Galileo mission of NASA. A two-dimensional generalization of the sequences has foundapplications in pattern recognition. Finally, today it hasa few applications in the rapidly developing area of DNA storage.

The talk will cover the diverse generalizations and applications of the graph throughout the last eighty years.

Special attention will be given to its applications to the topics which combine some elements from biology.