{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-9714"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-9714","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Discrete Models and Algorithms for Analyzing DNA Rearrangements","abstract":"In this work, language and tools are introduced, which model many-to-many mappings that comprise DNA rearrangements in nature. Existing theoretical models and data processing methods depend on the premise that DNA segments in the rearrangement precursor are in a clear one-to-one correspondence with their destinations in the recombined product. However, ambiguities in the rearrangement maps obtained from the ciliate species Oxytricha trifallax violate this assumption demonstrating a necessity for the adaptation of theory and practice. In order to take into account the ambiguities in the rearrangement maps, generalizations of existing recombination models are proposed. Edges in an ordered graph model the relative positions of precursor DNA segments and their labels indicate the orientations and destinations in the product genome. Properties of these structures are introduced with the intention to narrow down the space of possible rearrangements that can be described by the model to include only the types of complexities that appear in nature. The various subspaces of rearrangements defined by these properties are explored via a series of combinatorial counting results. The new model is applied to sequencing data of O. trifallax to assess the extent to which these properties describe the rearrangements this organism undergoes. To reduce the filtering of data, an algorithm which annotates the rearranging segments in precursor and product genomes without discarding ambiguities is presented. Furthermore, a generalization of the notion of scrambling that can be applied to such ambiguous rearrangement maps is defined. An algorithm that detects the generalized scrambling property in ambiguous rearrangement maps is also presented. Next, a computational tool implementing the two algorithms is introduced and tested. The annotation algorithm involves a step by which gapped sequence alignments are obtained from ungapped sequence alignments in an efficient and controlled manner. This method of combining ungapped alignments gives rise to another algorithm that can be applied to the more general problem of efficiently detecting gapped sequence alignments, which is implemented and tested in this work.","abstract_html":"In this work, language and tools are introduced, which model many-to-many mappings that comprise DNA rearrangements in nature. Existing theoretical models and data processing methods depend on the premise that DNA segments in the rearrangement precursor are in a clear one-to-one correspondence with their destinations in the recombined product. However, ambiguities in the rearrangement maps obtained from the ciliate species Oxytricha trifallax violate this assumption demonstrating a necessity for the adaptation of theory and practice. In order to take into account the ambiguities in the rearrangement maps, generalizations of existing recombination models are proposed. Edges in an ordered graph model the relative positions of precursor DNA segments and their labels indicate the orientations and destinations in the product genome. Properties of these structures are introduced with the intention to narrow down the space of possible rearrangements that can be described by the model to include only the types of complexities that appear in nature. The various subspaces of rearrangements defined by these properties are explored via a series of combinatorial counting results. The new model is applied to sequencing data of O. trifallax to assess the extent to which these properties describe the rearrangements this organism undergoes. To reduce the filtering of data, an algorithm which annotates the rearranging segments in precursor and product genomes without discarding ambiguities is presented. Furthermore, a generalization of the notion of scrambling that can be applied to such ambiguous rearrangement maps is defined. An algorithm that detects the generalized scrambling property in ambiguous rearrangement maps is also presented. Next, a computational tool implementing the two algorithms is introduced and tested. The annotation algorithm involves a step by which gapped sequence alignments are obtained from ungapped sequence alignments in an efficient and controlled manner. This method of combining ungapped alignments gives rise to another algorithm that can be applied to the more general problem of efficiently detecting gapped sequence alignments, which is implemented and tested in this work.","abstract_has_math":false,"creators":["Braun, Jasper"],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Mathematics and Statistics","degree_department":null,"school":null,"contributors":["Nataša Jonoska, Ph.D.","Masahico Saito, Ph.D.","Brendan T. Nagle, Ph.D.","Margaret A. Park, Ph.D.","Dmytro Savchuk, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-11-11T08:00:00Z","date_published":"2020-11-11T08:00:00Z","updated_at":"2026-11-19T08:44:51Z","subjects":["Ciliate genomics","Sequence alignment algorithms","Edge labellings","Ordered graphs","Bioinformatics","Computer Sciences","Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/8517","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/8517","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-9714","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nataša Jonoska, Ph.D.","Masahico Saito, Ph.D.","Brendan T. Nagle, Ph.D.","Margaret A. Park, Ph.D.","Dmytro Savchuk, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Braun, Jasper"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-11-11T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics and Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Ciliate genomics","Sequence alignment algorithms","Edge labellings","Ordered graphs","Bioinformatics","Computer Sciences","Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/8517"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this work, language and tools are introduced, which model many-to-many mappings that comprise DNA rearrangements in nature. Existing theoretical models and data processing methods depend on the premise that DNA segments in the rearrangement precursor are in a clear one-to-one correspondence with their destinations in the recombined product. However, ambiguities in the rearrangement maps obtained from the ciliate species Oxytricha trifallax violate this assumption demonstrating a necessity for the adaptation of theory and practice. In order to take into account the ambiguities in the rearrangement maps, generalizations of existing recombination models are proposed. Edges in an ordered graph model the relative positions of precursor DNA segments and their labels indicate the orientations and destinations in the product genome. Properties of these structures are introduced with the intention to narrow down the space of possible rearrangements that can be described by the model to include only the types of complexities that appear in nature. The various subspaces of rearrangements defined by these properties are explored via a series of combinatorial counting results. The new model is applied to sequencing data of O. trifallax to assess the extent to which these properties describe the rearrangements this organism undergoes. To reduce the filtering of data, an algorithm which annotates the rearranging segments in precursor and product genomes without discarding ambiguities is presented. Furthermore, a generalization of the notion of scrambling that can be applied to such ambiguous rearrangement maps is defined. An algorithm that detects the generalized scrambling property in ambiguous rearrangement maps is also presented. Next, a computational tool implementing the two algorithms is introduced and tested. The annotation algorithm involves a step by which gapped sequence alignments are obtained from ungapped sequence alignments in an efficient and controlled manner. This method of combining ungapped alignments gives rise to another algorithm that can be applied to the more general problem of efficiently detecting gapped sequence alignments, which is implemented and tested in this work."]},{"key":"dc:title","label":"Title","values":["Discrete Models and Algorithms for Analyzing DNA Rearrangements"]}]}],"canonical_facts":{"dc:contributor":["Nataša Jonoska, Ph.D.","Masahico Saito, Ph.D.","Brendan T. Nagle, Ph.D.","Margaret A. Park, Ph.D.","Dmytro Savchuk, Ph.D."],"dc:creator":["Braun, Jasper"],"dc:date":["2020-11-11T08:00:00Z"],"dc:description":["In this work, language and tools are introduced, which model many-to-many mappings that comprise DNA rearrangements in nature. Existing theoretical models and data processing methods depend on the premise that DNA segments in the rearrangement precursor are in a clear one-to-one correspondence with their destinations in the recombined product. However, ambiguities in the rearrangement maps obtained from the ciliate species Oxytricha trifallax violate this assumption demonstrating a necessity for the adaptation of theory and practice. In order to take into account the ambiguities in the rearrangement maps, generalizations of existing recombination models are proposed. Edges in an ordered graph model the relative positions of precursor DNA segments and their labels indicate the orientations and destinations in the product genome. Properties of these structures are introduced with the intention to narrow down the space of possible rearrangements that can be described by the model to include only the types of complexities that appear in nature. The various subspaces of rearrangements defined by these properties are explored via a series of combinatorial counting results. The new model is applied to sequencing data of O. trifallax to assess the extent to which these properties describe the rearrangements this organism undergoes. To reduce the filtering of data, an algorithm which annotates the rearranging segments in precursor and product genomes without discarding ambiguities is presented. Furthermore, a generalization of the notion of scrambling that can be applied to such ambiguous rearrangement maps is defined. An algorithm that detects the generalized scrambling property in ambiguous rearrangement maps is also presented. Next, a computational tool implementing the two algorithms is introduced and tested. The annotation algorithm involves a step by which gapped sequence alignments are obtained from ungapped sequence alignments in an efficient and controlled manner. This method of combining ungapped alignments gives rise to another algorithm that can be applied to the more general problem of efficiently detecting gapped sequence alignments, which is implemented and tested in this work."],"dc:identifier":["https://digitalcommons.usf.edu/etd/8517"],"dc:subject":["Ciliate genomics","Sequence alignment algorithms","Edge labellings","Ordered graphs","Bioinformatics","Computer Sciences","Mathematics"],"dc:title":["Discrete Models and Algorithms for Analyzing DNA Rearrangements"],"thesis:degree_discipline":["Mathematics and Statistics"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:44:51Z"}