Constructing Tree-Child Networks from Distance Matrices

Bordewich, Magnus; Semple, Charles; Tokac, Nihan

Abstract

A tree-child network is a phylogenetic network with the property that each non-leaf vertex is the parent of a tree vertex or a leaf. In this paper, we show that a tree-child network on taxa (leaf) set X with an outgroup and a positive real-valued weighting of its edges is essentially determined by the multi-set of all path-length distances between elements in X provided, for each reticulation, the edges directed into it have equal weight. Furthermore, we give a polynomial-time algorithm for reconstructing such a network from this inter-taxa distance information. Such constructions are of central importance in evolutionary biology where phylogenetic networks represent the ancestral history of a collection of present-day taxa.

Citation

Bordewich, M., Semple, C., & Tokac, N. (2017). Constructing Tree-Child Networks from Distance Matrices. Algorithmica, 80(8), 2240-2259. https://doi.org/10.1007/s00453-017-0320-6

• Journal Article Type: Article
• Acceptance Date: Apr 27, 2017
• Online Publication Date: May 8, 2017
• Publication Date: Aug 1, 2017
• Deposit Date: Apr 27, 2017
• Publicly Available Date: May 8, 2018
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 80
• Issue: 8
• Pages: 2240-2259
• DOI: https://doi.org/10.1007/s00453-017-0320-6
• Public URL: https://durham-repository.worktribe.com/output/1380623