Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements
| dc.contributor.author | Chen, Xiaofeng | en |
| dc.contributor.committeechair | Reidys, Christian Michael | en |
| dc.contributor.committeemember | Mortveit, Henning S. | en |
| dc.contributor.committeemember | Haskell, Peter E. | en |
| dc.contributor.committeemember | Floyd, William J. | en |
| dc.contributor.department | Mathematics | en |
| dc.date.accessioned | 2017-04-28T06:21:25Z | en |
| dc.date.available | 2017-04-28T06:21:25Z | en |
| dc.date.issued | 2017-04-27 | en |
| dc.description.abstract | Maps have been extensively studied and are important in many research fields. A map is a 2-cell embedding of a graph on an orientable surface. Motivated by a new way to read the information provided by the skeleton of a map, we introduce new objects called plane permutations. Plane permutations not only provide new insight into enumeration of maps and related graph embedding problems, but they also provide a powerful framework to study less related genome rearrangement problems. As results, we refine and extend several existing results on enumeration of maps by counting plane permutations filtered by different criteria. In the spirit of the topological, graph theoretical study of graph embeddings, we study the behavior of graph embeddings under local changes. We obtain a local version of the interpolation theorem, local genus distribution as well as an easy-to-check necessary condition for a given embedding to be of minimum genus. Applying the plane permutation paradigm to genome rearrangement problems, we present a unified simple framework to study transposition distances and block-interchange distances of permutations as well as reversal distances of signed permutations. The essential idea is associating a plane permutation to a given permutation or signed permutation to sort, and then applying the developed plane permutation theory. | en |
| dc.description.abstractgeneral | This work is mainly concerned with studying two problems. The first problem starts with a graph <i>G</i> consisting of vertices and lines (called edges) linking some pairs of vertices. Intuitively, if the graph <i>G</i> can not be drawn on the sphere without crossing edges, it may be possibly drawn on a torus (i.e., the surface of a doughnut) without crossing edges; if it is still impossible, it may be possible to draw the graph <i>G</i> on the surface obtained by “gluing” several tori together. Once a graph <i>G</i> is drawn on a surface without crossing edges, there is a cyclic order of those edges incident to each vertex of the graph. Suppose you are not satisfied with how the edges around a vertex are cyclically arranged, and you want to arrange them differently. A question that arises naturally would be: is the adjusted drawing still cross-free on the original surface, or do we need to glue more (or fewer) tori in order for it to be crossfree? The second problem stems from genome rearrangements. In bioinformatics, people try to understand evolution (of species) by comparing the genome sequences (e.g., DNA sequences) of different species. Certain operations on genome sequences are believed to be potential ways of how species evolve. The operations studied in this work are transpositions, block-interchanges and reversals. For example, a transposition is such an operation that swaps two consecutive segments on the given genome sequence. As a candidate indicator of how far away one species is from another from an evolutionary perspective, we can compute how many transpositions are required to transform the genome sequence of one species to that of the other. In this work, we propose a plane permutation framework, which works effectively on solving the above mentioned two problems. In addition, plane permutations themselves are interesting objects to study and are studied as well. | en |
| dc.description.degree | Ph. D. | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:10619 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/77535 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | Plane Permutation | en |
| dc.subject | Map | en |
| dc.subject | Graph Embedding | en |
| dc.subject | Genome Rearrangement | en |
| dc.title | Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements | en |
| dc.type | Dissertation | en |
| thesis.degree.discipline | Mathematics | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | doctoral | en |
| thesis.degree.name | Ph. D. | en |