Abstract
Phylogenetic networks are a generalization of phylogenetic trees that allow for representation of reticulate evolution. Recently, a space of unrooted phylogenetic networks was introduced, where such a network is a connected graph in which every vertex has degree 1 or 3 and whose leafset is a fixed set X of taxa. This space, denoted N(X)N(X) , is defined in terms of two operations on networks—the nearest neighbor interchange and triangle operations—which can be used to transform any network with leaf set X into any other network with that leaf set. In particular, it gives rise to a metric d on N(X)N(X) which is given by the smallest number of operations required to transform one network in N(X)N(X) into another in N(X)N(X) . The metric generalizes the wellknown NNImetric on phylogenetic trees which has been intensively studied in the literature. In this paper, we derive a bound for the metric d as well as a related metric dNNIdNNI which arises when restricting d to the subset of N(X)N(X) consisting of all networks with 2(X−1+i)2(X−1+i) vertices, i≥1i≥1 . We also introduce two new metrics on networks—the SPR and TBR metrics—which generalize the metrics on phylogenetic trees with the same name and give bounds for these new metrics. We expect our results to eventually have applications to the development and understanding of network search algorithms.
Original language  English 

Pages (fromto)  1229–1248 
Number of pages  20 
Journal  Journal of Mathematical Biology 
Volume  76 
Issue number  5 
Early online date  23 Aug 2017 
DOIs  
Publication status  Published  Apr 2018 
Keywords
 Phylogenetic networks
 Spaces of phylogenetic networks
 Phylogenetic network metrics
 Nearestneighbor interchange (NNI)
 Diameter
Profiles

Katharina Huber
 School of Computing Sciences  Associate Professor
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Taoyang Wu
 School of Computing Sciences  Lecturer in Computing Sciences
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research