arXiv preprint ·
Algorithms for Soft Tree Containment on Tree-Child Networks
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Phylogenetic networks generalize evolutionary trees by allowing lineages to merge. The Tree Containment problem asks whether a network $N$ displays a tree $T$ on the same taxa. When the polytomies of $T$ reflect uncertainty rather than simultaneous divergence, the relevant notion is soft display, in which $N$ may refine the polytomies of $T$. We take it in its asymmetric reading. Soft Tree Containment is NP-hard on reticulation-visible networks even at reticulation indegree three, and it was open for a non-binary tree and a tree-child network with multifurcating tree nodes or reticulations of indegree above two. We solve this case. A cluster characterization reduces soft display to realizing all clusters of $T$ by one switching, and in a tree-child network the vertices that can realize a cluster lie on a single chain. The per-cluster requirements then form a constraint network of width one, which arc consistency decides without search, and a $2$-SAT instance when $N$ is binary. This yields, to our knowledge, the first polynomial-time algorithm for soft Tree Containment on single-labelled tree-child networks of arbitrary reticulation indegree, and a linear-time algorithm when $T$ is binary. The same method decides the symmetric variant of the problem, in which the polytomies of $N$ may be resolved as well.
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
Evolutionary games on networks with negative edge-based environmental feedback
Mesoscopic derivation of predator-prey dynamics via diffusive fast-reaction asymptotics: cross-diffusion and fear effects
Bayesian inverse problems and epidemic-threshold uncertainty for a heterogeneous SIS reaction-diffusion model
Rule-table structure of life-like cellular automata: activity, asymmetry, sensitivity, and the propagation storage factorisation
Universal Infectious Disease Forecasting with Mantis 2
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.