Properties of Graphs Used to Model DNA Recombination

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