We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Recovering normal networks from shortest inter-taxa distance information.

Bordewich, Magnus and Huber, Katharina T. and Moulton, Vincent and Semple, Charles (2018) 'Recovering normal networks from shortest inter-taxa distance information.', Journal of mathematical biology., 77 (3). pp. 571-594.


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 have no “shortcuts”, that is, the networks are normal, 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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:06 February 2018
Date deposited:19 February 2018
Date of first online publication:24 February 2018
Date first made open access:24 February 2019

Save or Share this output

Look up in GoogleScholar