Degree Granting Department
Mathematics and Statistics
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.
Scholar Commons Citation
Arredondo, Ryan, "Properties of Graphs Used to Model DNA Recombination" (2014). Graduate Theses and Dissertations.