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.
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.
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.
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.
Finally, we discuss some work that might be pursued based off of the results in this paper.
|Commitee:||Bergman, Clifford, Fernandez-Baca, David, Martin, Ryan, Wu, Zhijun|
|School:||Iowa State University|
|School Location:||United States -- Iowa|
|Source:||DAI-B 73/10(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Mathematics, Bioinformatics, Computer science|
|Keywords:||Graph theory, Hybridization, Normal networks, Phylogenetics|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be