arXiv preprint ·
NOC NOC, who's there? Clustering systems of tree-child and normal networks
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Clustering systems provide a natural way to encode structural information contained in phylogenetic networks. In this note, we study the clustering systems of normal and tree-child networks through an overlap-based property of set systems, called not-overlap-covered (NOC). We show that the NOC property is equivalent to inclusion-visibility, a memberwise formulation of the strict-compatibility condition previously used for tree-child clustering systems. We characterize normal networks as precisely the semi-regular networks whose clustering systems satisfy NOC. Consequently, a clustering system is realized by a normal network if and only if it satisfies NOC, or equivalently, if every one of its clusters is inclusion-visible. In this case, the Hasse diagram provides a canonical normal realization. These are exactly the clustering systems realized by tree-child networks. The NOC formulation yields a sharp quadratic upper bound on the number of distinct clusters of tree-child and normal networks and a direct polynomial-time recognition algorithm. Finally, we explore several consequences of the NOC perspective beyond the phylogenetic setting. These include connections to the enumeration of normal networks, an order-theoretic interpretation of inclusion-visibility, structural properties of NOC set systems, and a tractable special case of Minimum Set Cover, which is NP-hard in general.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Big Brains and Changing Environments: Cause or Consequence?
BME-like Quartet Weights for Phylogenetic Trees
The evolution of sex for artificial intelligence: a population-genetic framework for multigenerational model populations
Self-Replicating Neural Cellular Automata: Quantifying Emergent Phenotypic and Genotypic Diversity in an OpenEnded Substrate
SAGE: A sampling-aware global evaluation benchmark for species distribution modeling
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.