Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks
From MaRDI portal
Publication:6056548
Abstract: In the context of reconstructing phylogenetic networks from a collection of phylogenetic trees, several characterisations and subsequently algorithms have been established to reconstruct a phylogenetic network that collectively embeds all trees in the input in some minimum way. For many instances however, the resulting network also embeds additional phylogenetic trees that are not part of the input. However, little is known about these inferred trees. In this paper, we explore the relationships among all phylogenetic trees that are embedded in a given phylogenetic network. First, we investigate some combinatorial properties of the collection P of all rooted binary phylogenetic trees that are embedded in a rooted binary phylogenetic network N. To this end, we associated a particular graph G, which we call rSPR graph, with the elements in P and show that, if |P|=2^k, where k is the number of vertices with in-degree two in N, then G has a Hamiltonian cycle. Second, by exploiting rSPR graphs and properties of hypercubes, we turn to the well-studied class of rooted binary level-1 networks and give necessary and sufficient conditions for when a set of rooted binary phylogenetic trees can be embedded in a level-1 network without inferring any additional trees. Lastly, we show how these conditions translate into a polynomial-time algorithm to reconstruct such a network if it exists.
Recommendations
- Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
- Display sets of normal and tree-child networks
- Reconstruction of certain phylogenetic networks from the genomes at their leaves
- Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
- A class of phylogenetic networks reconstructable from ancestral profiles
Cites work
- A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
- Another characterization of hypercubes
- Bounding the number of hybridisation events for a consistent evolutionary history
- Classes of explicit phylogenetic networks and their biological and mathematical significance
- Combinatorial Gray codes -- an updated survey
- Comparison of labeled trees with valency three
- Counting phylogenetic networks
- Efficient algorithms for inferring evolutionary trees
- Efficiently inferring pairwise subtree prune-and-regraft adjacencies between phylogenetic trees
- Faster computation of the Robinson-Foulds distance between phylogenetic networks
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- Introduction to algorithms.
- Locating a tree in a phylogenetic network
- Non-essential arcs in phylogenetic networks
- On the complexity of comparing evolutionary trees
- On the complexity of testing a graph for n-cube
- On the computational complexity of the rooted subtree prune and regraft distance
- Optimal algorithms for comparing trees with labeled leaves
- Research in Computational Molecular Biology
- Subtree transfer operations and their induced metrics on evolutionary trees
Cited in
(2)
This page was built for publication: Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056548)
