Kuang-Yu Chang, Yun Cui, Siu-Ming Yiu, Wing-Kai Hon

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 [Formula: see text] is equal to the shortest distance between X and Y in N), we can re-construct a network that satisfies M in [Formula: see text] 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 [Formula: see text] space, such that on any given phylogenetic tree T, we can determine whether T is contained in N (i.e., if a spanning subtree [Formula: see text] of N is a subdivision of T) in [Formula: see text] time.