Approximation Algorithms for Constructing Evolutionary Trees

Abstract

In this paper, we shall propose heuristic algorithms to construct evolutionary trees under the distance base model. When the distance matrix is metric, the problem is called the triangle minimum ultrametric tree problem . We shall also propose a heuristic algorithm to obtain a good leaf node circular order. The heuristic algorithm is based on the clustering scheme. And then we shall design a dynamic programming algorithm to construct the optimal ultrametric tree under some fixed leaf node circular order.