Recovering normal networks from shortest inter-taxa distance information

Bordewich, Magnus, Huber, Katharina T., Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Semple, Charles (2018) Recovering normal networks from shortest inter-taxa distance information. Journal of Mathematical Biology, 77 (3). 571–594. ISSN 0303-6812

Preview

PDF (Accepted manuscript) - Accepted Version Download (314kB) | Preview

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.

Item Type:	Article
Uncontrolled Keywords:	normal phylogenetic network,distance ,tree-child,edge-weighting,algorithm
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Pure Connector
Date Deposited:	13 Feb 2018 11:30
Last Modified:	14 Jun 2023 13:17
URI:	https://ueaeprints.uea.ac.uk/id/eprint/66285
DOI:	10.1007/s00285-018-1218-x

Downloads

Actions (login required)

View Item