Approximation Algorithms for Constructing Evolutionary Trees
Chia-Mao Huang, Chang‐Biau Yang · 2006
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 ( MUT). For the MUT, we shall propose an approximation algorithm, with error ratio logn 1, where a . 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. The time complexity of the dynamic programming is , if the scoring function is the minimum -min increment.