English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Phylogenetic networks are a flexible model of evolution that can representreticulate evolution and handle complex data. Tree-based networks, which arephylogenetic networks that have a spanning tree with the same root and leaf-setas the network itself, have been well studied. However, not all networks aretree-based. Francis-Semple-Steel (2018) thus introduced several indices tomeasure the deviation of rooted binary phylogenetic networks $N$ from beingtree-based, such as the minimum number $\delta^\ast(N)$ of additional leavesneeded to make $N$ tree-based, and the minimum difference $\eta^\ast(N)$between the number of vertices of $N$ and the number of vertices of a subtreeof $N$ that shares the root and leaf set with $N$. Hayamizu (2021) hasestablished a canonical decomposition of almost-binary phylogenetic networks of$N$, called the maximal zig-zag trail decomposition, which has manyimplications including a linear time algorithm for computing $\delta^\ast(N)$.The Maximum Covering Subtree Problem (MCSP) is the problem of computing$\eta^\ast(N)$, and Davidov et al. (2022) showed that this can be solved inpolynomial time (in cubic time when $N$ is binary) by an algorithm for theminimum cost flow problem. In this paper, under the assumption that $N$ isalmost-binary (i.e. each internal vertex has in-degree and out-degree at mosttwo), we show that $\delta^\ast(N)\leq \eta^\ast (N)$ holds, which is tight,and give a characterisation of such phylogenetic networks $N$ that satisfy$\delta^\ast(N)=\eta^\ast(N)$. Our approach uses the canonical decomposition of$N$ and focuses on how the maximal W-fences (i.e. the forbidden subgraphs oftree-based networks) are connected to maximal M-fences in the network $N$. Ourresults introduce a new class of phylogenetic networks for which MCSP can besolved in linear time, which can be seen as a generalisation of tree-basednetworks.

Rooted Almost-binary Phylogenetic Networks for which the Maximum Covering Subtree Problem is Solvable in Linear Time