Recovering normal networks from shortest inter-taxa distance information

DOI10.1007/S00285-018-1218-XzbMATH Open1406.05098arXiv1711.08866OpenAlexW2789052566WikidataQ52686592 ScholiaQ52686592MaRDI QIDQ667692FDOQ667692

Authors: Magnus Bordewich, Katharina T. Huber, Charles Semple, Vincent Moulton 

Publication date: 1 March 2019

Published in: Journal of Mathematical Biology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1711.08866

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

zbMATH Keywords

distance matrixtree-child networknormal network

Mathematics Subject Classification ID

Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20) Systems biology, networks (92C42) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Title not available (Why is that?)
• A note on the metric properties of trees
• A note on the tree realizability of a distance matrix
• Title not available (Why is that?)
• Counting phylogenetic networks
• Determining phylogenetic networks from inter-taxa distances
• An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
• Properties of normal phylogenetic networks
• Beyond representing orthology relations by trees
• Unique determination of some homoplasies at hybridization events
• Reconstruction of some hybrid phylogenetic networks with homoplasies from distances
• Constructing tree-child networks from distance matrices

Cited In (13)

• Identifiability of local and global features of phylogenetic networks from average distances
• Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
• Determining triangulations and quadrangulations by boundary distances
• Level-\(2\) networks from shortest and longest distances
• Properties of normal phylogenetic networks
• Classes of explicit phylogenetic networks and their biological and mathematical significance
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
• Defining phylogenetic networks using ancestral profiles
• Shared ancestry graphs and symbolic arboreal maps
• Anomalous networks under the multispecies coalescent: theory and prevalence
• A class of phylogenetic networks reconstructable from ancestral profiles
• Identifying circular orders for blobs in phylogenetic networks
• 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)