Date of Award
Spring 2019
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Joshua Cooper
Abstract
Motivated by the study of genomes evolving by reversals, the primary topic of this thesis is “successful pressing sequences” in simple pseudo-graphs. Pressing sequences where first introduced by Hannenhali and Pevzner in 1999 where they showed that sorting signed permutation problem can be solved in polynomial time, therefore demonstrating that the length of a most parsimonious solution to the genome in- version only rearrangement problem can be determined efficiently.
A signed permutation is an integer permutation where each entry is given a sign: plus or minus. A reversal in a signed permutation is the operation of reversing a subword and flipping the signs of the subword’s entries. The primary computational problem of sorting signed permutations by reversals is to find the minimum number of reversals needed to transform a signed permutation into the positive identity per- mutation. Hannenhalli and Pevzner showed that the signed sorting problem can be solved in polynomial-time in contrast to the problem of sorting unsigned permuta- tions, which is known to be NP-hard in general. At the core of the argument given by Hannenhali and Pevzner is the study of successful pressing sequences on vertex 2-colored graphs.
The connection between permutation sorting and phylogenetics dates back to at least the 1930’s, when two biologists, Dobzhansky and Sturtevant, wrote a series of papers in which they argued that the relationships between possible gene arrange- ments within a given chromosome encode critical information about the evolutionary history of species containing those genomes. In particular, they introduced the idea that the degree of disorder between the genes in two genomes is an indicator of the evolutionary distance between two organisms. This has inspired extensive work in the fields of computational biology, bio-informatics and phylogenetics. In particular, researchers have pursued the question of how a common ancestral genome may have been transformed by evolutionary events into distinct, yet homologous, genomes. In mathematics and computer science, we often represent genomes as signed permuta- tions (signed since DNA is oriented between two strands) and evolutionary events are encoded as operations on signed permutations. Among the most studied operations are block transpositions, prefix-reversals, and reversals, all of which correspond to common evolutionary mechanisms.
In addition to the study of pressing sequences in simple pseudo-graphs, in this thesis we discuss related topics such as Cholesky factorizations of matrices over finite- fields, a sampling algorithm to generate simple pseudo-graphs uniformly at random, and the complexity of the “pressing space” of a simple pseudo-graph (the space of all successful pressing sequences of a simple pseudo-graph). This work includes collab- orative work with Dr. Joshua Cooper (Mathematics, University of South Carolina), M.S. graduate Erin Hanna (Mathematics, University of South Carolina), and M.S. candidate Peter Gartland (Mathematics, University of South Carolina).
Rights
© 2019, Hays Wimsatt Whitlatch
Recommended Citation
Whitlatch, H. W.(2019). Successful Pressing Sequences in Simple Pseudo-Graphs. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5135