An Approximate Algorithm for Evolutionary Tree Reconstruction from Distance Matrix

Abstract

Most optimization problems for evolutionary tree reconstruction from distance matrix are either NP-complete or still unknown. In this paper, we present an approximate algorithm under an important optimization criteria：minimum tree size. Our algorithm runs in O(n³) time and constructs a tree which size is no more than 3 times of the optimal.