Graduation Year


Document Type




Degree Granting Department

Mathematics and Statistics

Major Professor

Natasha Jonoska

Co-Major Professor

Masahiko Saito


Chord diagrams, Ciliates, Double occurrence words, Orientable genus of graphs, Ribbon graphs


A model for DNA recombination uses 4-valent rigid vertex graphs,

called assembly graphs. An assembly graph,

similarly to the projection of knots, can be associated with an

unsigned Gauss code, or double occurrence word.

We define biologically motivated reductions that act on double

occurrence words and, in turn, on their associated assembly graphs. For

every double occurrence word w there is a sequence of reduction

operations that may be applied to w so that what remains is the

empty word, [epsilon]. Then the nesting index of a word w,

denoted by NI(w), is defined to to be the least number of reduction

operations necessary to reduce w to [epsilon]. The nesting index

is the first property of assembly graphs that we study. We use chord

diagrams as tools in our study of the nesting index. We observe two

double occurrence words that correspond to the same circle graph,

but that have arbitrarily large differences in nesting index values.

In 2012, Buck et al. considered the cellular

embeddings of assembly graphs into orientable surfaces. The genus

range of an assembly graph [Gamma], denoted gr([Gamma]), was defined to

be the set of integers g where g is the genus of an orientable

surface F into which [Gamma] cellularly embeds. The genus range is

the second property of assembly graphs that we study. We generalize

the notion of the genus range to that of the genus spectrum, where

for each g [isin] gr([Gamma]) we consider the number of orientable

surfaces F obtained from [Gamma] by a special construction, called a

ribbon graph construction, that have genus g. By

considering this more general notion we gain a better understanding

of the genus range property. Lastly, we show how one can obtain the

genus spectrum of a double occurrence word from the genus spectrums

of its irreducible parts, i.e., its double occurrence subwords.

In the final chapter we consider constructions of double occurrence

words that recognize certain values for nesting index and genus

range. In general, we find that for arbitrary values of nesting index

[ge] 2 and genus range, there is a double occurrence word that

recognizes those values.

Included in

Mathematics Commons