Recovering normal networks from shortest inter-taxa distance information
From MaRDI portal
(Redirected from Publication:667692)
Abstract: Phylogenetic networks are a type of leaf-labelled, acyclic, directed graph used by biologists to represent the evolutionary history of species whose past includes reticulation events. A phylogenetic network is tree-child if each non-leaf vertex is the parent of a tree vertex or a leaf. Up to a certain equivalence, it has been recently shown that, under two different types of weightings, edge-weighted tree-child networks are determined by their collection of distances between each pair of taxa. However, the size of these collections can be exponential in the size of the taxa set. In this paper, we show that, if we ignore redundant edges, the same results are obtained with only a quadratic number of inter-taxa distances by using the shortest distance between each pair of taxa. The proofs are constructive and give cubic-time algorithms in the size of the taxa sets for building such weighted networks.
Recommendations
- Constructing tree-child networks from distance matrices
- Determining phylogenetic networks from inter-taxa distances
- Reconstruction of certain phylogenetic networks from their tree-average distances
- Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
- An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
Cites work
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 3243264 (Why is no real title available?)
- A note on the metric properties of trees
- A note on the tree realizability of a distance matrix
- An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
- Beyond representing orthology relations by trees
- Constructing tree-child networks from distance matrices
- Counting phylogenetic networks
- Determining phylogenetic networks from inter-taxa distances
- Properties of normal phylogenetic networks
- Reconstruction of some hybrid phylogenetic networks with homoplasies from distances
- Unique determination of some homoplasies at hybridization events
Cited in
(15)- Shared ancestry graphs and symbolic arboreal maps
- Classes of explicit phylogenetic networks and their biological and mathematical significance
- Identifying circular orders for blobs in phylogenetic networks
- Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
- Properties of normal phylogenetic networks
- Determining phylogenetic networks from inter-taxa distances
- A class of phylogenetic networks reconstructable from ancestral profiles
- An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
- Determining triangulations and quadrangulations by boundary distances
- Level-\(2\) networks from shortest and longest distances
- Identifiability of local and global features of phylogenetic networks from average distances
- Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
- Anomalous networks under the multispecies coalescent: theory and prevalence
- Defining phylogenetic networks using ancestral profiles
- Caterpillars on three and four leaves are sufficient to binary normal networks
This page was built for publication: Recovering normal networks from shortest inter-taxa distance information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q667692)
