Spelling suggestions: "subject:"double occurrence words"" "subject:"double occurrence bords""
1 |
Properties of Graphs Used to Model DNA RecombinationArredondo, Ryan 21 March 2014 (has links)
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.
|
2 |
Patterns in Words Related to DNA RearrangementsNabergall, Lukas 30 June 2017 (has links)
Patterns, sequences of variables, have traditionally only been studied when morphic images of them appear as factors in words. In this thesis, we initiate a study of patterns in words that appear as subwords of words. We say that a pattern appears in a word if each pattern variable can be morphically mapped to a factor in the word. To gain insight into the complexity of, and similarities between, words, we define pattern indices and distances between two words relative a given set of patterns. The distance is defined as the minimum number of pattern insertions and/or removals that transform one word into another. The pattern index is defined as the minimum number of pattern removals that transform a given word into the empty word. We initially consider pattern distances between arbitrary words. We conjecture that the word distance is computable relative the pattern αα and prove a lemma in this direction. Motivated by patterns detected in certain scrambled ciliate genomes, we focus on double occurrence words (words where every symbol appears twice) and consider recursive patterns, a generalization of the notion of a pattern which includes new types of words. We show that in double occurrence words the distance relative so-called complete sets of recursive patterns is computable. In particular, the pattern distance relative patterns αα (repeat words) and ααR (return words) is computable for double occurrence words. We conclude by applying pattern indices and word distances towards the analysis of highly scrambled genes in O. trifallax and discover a common pattern.
|
3 |
Recursive Methods in Number Theory, Combinatorial Graph Theory, and ProbabilityBurns, Jonathan 07 July 2014 (has links)
Recursion is a fundamental tool of mathematics used to define, construct, and analyze mathematical objects. This work employs induction, sieving, inversion, and other recursive methods to solve a variety of problems in the areas of algebraic number theory, topological and combinatorial graph theory, and analytic probability and statistics. A common theme of recursively defined functions, weighted sums, and cross-referencing sequences arises in all three contexts, and supplemented by sieving methods, generating functions, asymptotics, and heuristic algorithms.
In the area of number theory, this work generalizes the sieve of Eratosthenes to a sequence of polynomial values called polynomial-value sieving. In the case of quadratics, the method of polynomial-value sieving may be characterized briefly as a product presentation of two binary quadratic forms. Polynomials for which the polynomial-value sieving yields all possible integer factorizations of the polynomial values are called recursively-factorable. The Euler and Legendre prime producing polynomials of the form n2+n+p and 2n2+p, respectively, and Landau's n2+1 are shown to be recursively-factorable. Integer factorizations realized by the polynomial-value sieving method, applied to quadratic functions, are in direct correspondence with the lattice point solutions (X,Y) of the conic sections aX2+bXY +cY2+X-nY=0. The factorization structure of the underlying quadratic polynomial is shown to have geometric properties in the space of the associated lattice point solutions of these conic sections.
In the area of combinatorial graph theory, this work considers two topological structures that are used to model the process of homologous genetic recombination: assembly graphs and chord diagrams. The result of a homologous recombination can be recorded as a sequence of signed permutations called a micronuclear arrangement. In the assembly graph model, each micronuclear arrangement corresponds to a directed Hamiltonian polygonal path within a directed assembly graph. Starting from a given assembly graph, we construct all the associated micronuclear arrangements. Another way of modeling genetic rearrangement is to represent precursor and product genes as a sequence of blocks which form arcs of a circle. Associating matching blocks in the precursor and product gene with chords produces a chord diagram. The braid index of a chord diagram can be used to measure the scope of interaction between the crossings of the chords. We augment the brute force algorithm for computing the braid index to utilize a divide and conquer strategy. Both assembly graphs and chord diagrams are closely associated with double occurrence words, so we classify and enumerate the double occurrence words based on several notions of irreducibility. In the area of analytic probability, moments abstractly describe the shape of a probability distribution. Over the years, numerous varieties of moments such as central moments, factorial moments, and cumulants have been developed to assist in statistical analysis. We use inversion formulas to compute high order moments of various types for common probability distributions, and show how the successive ratios of moments can be used for distribution and parameter fitting. We consider examples for both simulated binomial data and the probability distribution affiliated with the braid index counting sequence. Finally we consider a sequence of multiparameter binomial sums which shares similar properties with the moment sequences generated by the binomial and beta-binomial distributions. This sequence of sums behaves asymptotically like the high order moments of the beta distribution, and has completely monotonic properties.
|
Page generated in 0.0386 seconds