Metraipolis › archive › dc_5909e9becda8
The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks — arXiv:2610.23426
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.23426
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:37:51.548Z
- SHA-256 of the archived text
cfd80669797f844b298debd269642bc87e0a59bef8f24a04b7505cd94cb0cc75- Stable URL of this page
https://metraipolis.com/documento/dc_5909e9becda8
How to cite
The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks — arXiv:2610.23426 — arXiv (en), https://arxiv.org/abs/2610.23426 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5909e9becda8 (Metraipolis archive dc_5909e9becda8, sha256 cfd80669797f844b298debd269642bc87e0a59bef8f24a04b7505cd94cb0cc75)
BibTeX
@misc{dc5909e9becda8,
title = {The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks — arXiv:2610.23426},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.23426},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5909e9becda8; sha256 cfd80669797f844b298debd269642bc87e0a59bef8f24a04b7505cd94cb0cc75},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23426. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Tree-based networks are a broad graph class in phylogenetics which posit a model of evolution composed of tree-like processes and hybridization events. Hence, for any non-tree-based phylogenetic network, it is meaningful to study the magnitude of violation of the tree-based model assumptions. For rooted networks, we introduce the proximity measure delta_rNNI, defined by the minimum number of rooted nearest neighbor interchanges (NNIs) required to transform a network into a tree-based network. For binary networks, we prove that delta_rNNI is pairwise distinct from all previously known proximity measures in the literature and that no approximation guarantees between delta_rNNI and other known proximity measures holds. In addition, we characterize a family of networks for which a linear time lower bound on delta_rNNI is tight. Moreover, we analyze upper bounds and give an exact solution algorithm to compute delta_rNNI. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Populations and Evolution (q-bio.PE) ; Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2610.23426 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T09:33:44.758Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).