On normal networks

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>