Back to search

University of South Florida

Properties of Graphs Used to Model DNA Recombination

Abstract

dc:description

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.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Arredondo, Ryan
Contributors dc:contributor
  • Natasa Jonoska, Ph.D.
  • Masahiko Saito, Ph.D.
  • Dmytro Savchuk, Ph.D.

Subjects

dc:subject × 6

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/4979

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Arredondo, Ryan. Properties of Graphs Used to Model DNA Recombination. Thesis thesis, University of South Florida, 2014. https://digitalcommons.usf.edu/etd/4979