Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 53 min ago
PreprintarXiv licencearXiv

The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks

  • Martin Frohn
  • Takatora Suzuki
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Doublecortin mutation disrupts lattice-dependent proximity to reveal cytoskeletal networks in developing neurons
    B. L. Kelly, J. A. G. Haineault, L. M. Munter +2
    bioRxivPreprintAll rights reservedFull textDevelopmental biologybioRxiv
  2. Best Matches in Phylogenetic Networks
    Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
    arXivPreprintCC BY 4.0Full textEvolutionary biologyarXiv
  3. Exact Counts of Binary Phylogenetic Networks with Four Reticulations
    Hao Yu, Louxin Zhang
    arXivPreprintarXiv licenceFull textEvolutionary biologyCombinatorics & discrete mathematicsarXiv
  4. The parental parsimony problem on binary, tree-child phylogenetic networks
    Martin Frohn
    arXivPreprintarXiv licenceFull textEvolutionary biologyOptimisation & controlarXiv
  5. An explicit birth-death-reticulation model for studying the diversification of phylogenetic networks
    M. R. May, C. l. Rothfels
    bioRxivPreprintCC BY-NCFull textEvolutionary biologybioRxiv

Cite

BibTeXRIS
BibTeX
@misc{frohn2026nearest,
  title = {{The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks}},
  author = {Martin Frohn and Takatora Suzuki},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23426},
  eprint = {2610.23426},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23426},
}
RIS
TY  - UNPB
TI  - The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
AU  - Martin Frohn
AU  - Takatora Suzuki
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23426
UR  - https://arxiv.org/abs/2610.23426
AB  - 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.
ER  -