Skip to main content

Research Repository

Advanced Search

Recovering normal networks from shortest inter-taxa distance information

Bordewich, Magnus; Huber, Katharina T.; Moulton, Vincent; Semple, Charles

Recovering normal networks from shortest inter-taxa distance information Thumbnail


Authors

Katharina T. Huber

Vincent Moulton

Charles Semple



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 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.

Citation

Bordewich, M., Huber, K. T., Moulton, V., & Semple, C. (2018). Recovering normal networks from shortest inter-taxa distance information. Journal of Mathematical Biology, 77(3), 571-594. https://doi.org/10.1007/s00285-018-1218-x

Journal Article Type Article
Acceptance Date Feb 6, 2018
Online Publication Date Feb 24, 2018
Publication Date Sep 30, 2018
Deposit Date Feb 16, 2018
Publicly Available Date Feb 24, 2019
Journal Journal of Mathematical Biology
Print ISSN 0303-6812
Electronic ISSN 1432-1416
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 77
Issue 3
Pages 571-594
DOI https://doi.org/10.1007/s00285-018-1218-x

Files





You might also like



Downloadable Citations