Reconstructing One-Articulated Networks with Distance Matrices

Given a distance matrix M that represents evolutionary distances between any two species, an edge- weighted phylogenetic network N is said to satisfy M if between any pair of species, there exists a path in N with a length equal to the corresponding entry in M. In this article, we consider a special class of networks called a one- articulated network, which is a proper superset of galled trees. We show that if the distance matrix M is derived from an ultrametric one- articulated network N (i. e., for any species X and Y, the entry M(X, Y) is equal to the shortest distance between X and Y in N), we can re- construct a network that satisfies M in O(n2) time, where n denotes the number of species; further, the reconstructed network is guaranteed to be the simplest, in a sense that the number of hybrid nodes is minimized. In addition, one may easily index a one- articulated network N with a minimum number of hybrid nodes in O(n) space, such that on any given phylogenetic tree T, we can determine whether T is contained in N (i. e., if a spanning subtree T0 of N is a subdivision of T) in O(n) time.