How tree-based is my network? Proximity measures for unrooted phylogenetic networks
Tree-based networks are a class of phylogenetic networks that attempt to formally capture what is meant by "tree-like" evolution. A given non-tree-based phylogenetic network, however, might appear to be very close to being tree-based, or very far. In this paper, we formalise the notion of proximity to tree-based for unrooted phylogenetic networks, with a range of proximity measures. These measures also provide characterisations of tree-based networks. One measure in particular, related to the nearest neighbour interchange operation, allows us to define the notion of "tree-based rank". This provides a subclassification within the tree-based networks themselves, identifying those networks that are "very" tree-based. Finally, we prove results relating tree-based networks in the settings of rooted and unrooted phylogenetic networks, showing effectively that an unrooted network is tree-based if and only if it can be made a rooted tree-based network by rooting it and orienting the edges appropriately. This leads to a clarification of the contrasting decision problems for tree-based networks, which are polynomial in the rooted case but NP complete in the unrooted.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks
Phylogenetic networks which are, as opposed to trees, suitable to describe processes like hybridization and horizontal gene transfer, play a substantial role in evolutionary research. However, while non-treelike events n…
Tree-Based Unrooted Nonbinary Phylogenetic Networks
Phylogenetic networks are a generalisation of phylogenetic trees that allow for more complex evolutionary histories that include hybridisation-like processes. It is of considerable interest whether a network can be consi…
Leaping through tree space: continuous phylogenetic inference for rooted and unrooted trees
Phylogenetics is now fundamental in life sciences, providing insights into the earliest branches of life and the origins and spread of epidemics. However, finding suitable phylogenies from the vast space of possible tree…
The space of tree-based phylogenetic networks
Phylogenetic networks are generalizations of phylogenetic trees that allow the representation of reticulation events such as horizontal gene transfer or hybridization, and can also represent uncertainty in inference. A s…
On the existence of funneled orientations for classes of rooted phylogenetic networks
Recently, there has been a growing interest in the relationships between unrooted and rooted phylogenetic networks. In this context, a natural question to ask is if an unrooted phylogenetic network U can be oriented as a…