On normal networks

by Bickner, Devin Robert, Ph.D., IOWA STATE UNIVERSITY, 2012, 89 pages; 3511361


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.

AdviserStephen Willson
Source TypeDissertation
SubjectsApplied mathematics; Mathematics; Bioinformatics; Computer science
Publication Number3511361

About ProQuest Dissertations & Theses
With nearly 4 million records, the ProQuest Dissertations & Theses (PQDT) Global database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

PQDT Global combines content from a range of the world's premier universities - from the Ivy League to the Russell Group. Of the nearly 4 million graduate works included in the database, ProQuest offers more than 2.5 million in full text formats. Of those, over 1.7 million are available in PDF format. More than 90,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or contact ProQuest Support.