On normal networks

dc.contributor.advisor Stephen Willson
dc.contributor.author Bickner, Devin
dc.contributor.department Mathematics
dc.date 2018-08-11T08:40:40.000
dc.date.accessioned 2020-06-30T02:41:33Z
dc.date.available 2020-06-30T02:41:33Z
dc.date.copyright Sun Jan 01 00:00:00 UTC 2012
dc.date.embargo 2013-06-05
dc.date.issued 2012-01-01
dc.description.abstract <p>Phylogenetic trees have long been the standard object used in evolutionary biology to illustrate how a given set of species are related. Evidence is mounting to suggest that hybridization, historical events when multiple species merge to form new species, are prevalent enough to warrant inclusion into the field. Phylogenetic networks allow for this possibility.</p> <p>In this paper, we discuss normal networks, a specific type of network with desirable tree-like properties. We find tight upper and lower bounds for certain aspects of the networks, including the number of edges, normal edges, hybrid vertices, parents of a vertex, and children of a vertex. We also find tight upper and lower bounds on the number of vertices and edges of specific cases of normal networks, as well as various interesting, related results that lead to these counts.</p> <p>We discuss the tree containment problem, which asks whether a given network contains the information contained within a given tree. We give an algorithm and prove that the tree containment problem for normal networks is solvable in polynomial time.</p> <p>We also discuss new operations on normal networks that are based off of the subtree-pruning and regrafting operation, a standard phylogenetic tree operation. These new operations allow for us to navigate through normal network space, a graph that represents all normal networks with a given set of leaves in which an edge connecting two networks is present if one network can be obtained from the other using exactly one of the operations discussed. We show that these operations connect binary normal network space, the normal network space in which the normal networks have no more than two edges going into or out of each of vertex. These operations on this network space can be used to give better upper bounds on the number of binary normal networks. We show a few of these upper bounds, as well as compare them to upper bounds of trees and regular networks, a type of network that contains normal networks.</p> <p>Finally, we discuss some work that might be pursued based off of the results in this paper.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/12277/
dc.identifier.articleid 3284
dc.identifier.contextkey 3437642
dc.identifier.doi https://doi.org/10.31274/etd-180810-1598
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/12277
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/26466
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/12277/Bickner_iastate_0097E_12571.pdf|||Fri Jan 14 19:17:05 UTC 2022
dc.subject.disciplines Bioinformatics
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Mathematics
dc.subject.keywords Graph Theory
dc.subject.keywords Hybridization
dc.subject.keywords Normal Networks
dc.subject.keywords Phylogenetics
dc.title On normal networks
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
Name:
Bickner_iastate_0097E_12571.pdf
Size:
547.18 KB
Format:
Adobe Portable Document Format
Description: