Constructing Tree-Child Networks from Distance Matrices

Bordewich, Magnus; Semple, Charles; Tokac, Nihan

doi:10.1007/s00453-017-0320-6

Constructing Tree-Child Networks from Distance Matrices

Bordewich, Magnus; Semple, Charles; Tokac, Nihan

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

Charles Semple

Nihan Tokac

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