Francis, Andrew, Huber, Katharina T., Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2018) Bounds for phylogenetic network space metrics. Journal of Mathematical Biology, 76 (5). 1229–1248. ISSN 0303-6812
Preview |
PDF (Published manuscript)
- Published Version
Available under License Creative Commons Attribution. Download (689kB) | Preview |
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 leaf-set 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 well-known NNI-metric 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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | phylogenetic networks,spaces of phylogenetic networks,phylogenetic network metrics,nearest-neighbor interchange (nni),diameter |
Faculty \ School: | Faculty of Science > School of Computing Sciences |
UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation |
Depositing User: | Pure Connector |
Date Deposited: | 17 Aug 2017 05:05 |
Last Modified: | 09 Oct 2024 13:33 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/64529 |
DOI: | 10.1007/s00285-017-1171-0 |
Downloads
Downloads per month over past year
Actions (login required)
View Item |