Colorado State University undergraduate student Christie Burris, presented a poster at the MAA Undergraduate Student Poster Session at the Joint Math Meetings in San Antonio, Texas in January. With a total of 273 undergraduate posters submitted from, Burris won a top poster prize in the category of Graph Theory, for her poster on "Construction and Optimality of Unoriented de Bruijn Sequences."
Burris is shown with Dr. Francis Motta (currently a postdoc at Duke University), coadviser to Christie on her winning poster project. Also attending the MAA session was coadviser Patrick Shipman.
Christie Burris is currently an undergraduate student majority in mathematics. She is an active participant in the Mathematics Honors Program and Math Club.
Poster abstract: Construction and Optimality of Undirected de Bruijn Sequences
Christie Burris Colorado State University
CSU Advisor: Dr. Patrick Shipman
For positive integers k and n, what is the minimal length of a word over an alphabet of size k which contains every lengthn word as a subword? Clearly the minimum possible length of such a word is kn C n1, as this length is required to see all kn subwords without repetition. Words that achieve this bound are commonly referred to as de Bruijn sequences. Applications of de Bruijn sequences arise as optimally random sequences in coding theory as well as in the design of DNA microarrays. De Bruijn sequences on the alphabet corresponding to the set of amino acids, fA;D; C;Gg, which comprise DNA can be used to see a great variety of binding patterns relative to the length of the sequence. We introduce a variation on the idea of a de Bruijn sequence, as exemplified by the sequence 00010111.This sequence sees each of the binary words of length 3 as subwords with the minimal number or repetitions when read both lefttoright and righttoleft. We call such a sequence an undirected de Bruijn sequence. The purpose of this research is to determine the lengths of undirected de Bruijn sequences and develop methods for their construction.
