title: Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations.
abstract: Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that are used to represent the evolution of species which have undergone reticulate evolution. In this paper we consider spaces of such networks defined by some novel local operations that we introduce for converting one phylogenetic network into another. These operations are modeled on the well-studied nearest-neighbor interchange operations on phylogenetic trees, and lead to natural generalizations of the tree spaces that have been previously associated to such operations. We present several results on spaces of some relatively simple networks, called level-1 networks, including the size of the neighborhood of a fixed network, and bounds on the diameter of the metric defined by taking the smallest number of operations required to convert one network into another. We expect that our results will be useful in the development of methods for systematically searching for optimal phylogenetic networks using, for example, likelihood and Bayesian approaches.
authors.affiliation: School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK. katharina.huber@cmp.uea.ac.uk.
authors.forename: Katharina T
authors.initials: KT
authors.lastname: Huber
authors.affiliation: Department of Computer Science, University of Auckland, Auckland, New Zealand. s.linz@auckland.ac.nz.
authors.forename: Simone
authors.initials: S
authors.lastname: Linz
authors.affiliation: School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK. vincent.moulton@cmp.uea.ac.uk.
authors.forename: Vincent
authors.initials: V
authors.lastname: Moulton
authors.affiliation: School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK. taoyang.wu@gmail.com.
authors.forename: Taoyang
authors.initials: T
authors.lastname: Wu
mesh_terms: D000465:Algorithms; D001499:Bayes Theorem; D005075:Biological Evolution; D019295:Computational Biology; D016013:Likelihood Functions; D055641:Mathematical Concepts; D008954:Models, Biological; D010802:Phylogeny
keywords: Nearest-neighbor interchange (NNI); Phylogenetic networks; Phylogenetic tree metrics; Spaces of phylogenetic trees