1 |
Approximation Algorithms for Constructing Evolutionary TreesHuang, Chia-Mao 10 August 2001 (has links)
In this thesis, we shall propose heuristic algorithms to construct evolutionary trees under the distance base model. For a distance matrix of any type, the problem of constructing a minimum ultrametric tree (MUT), whose scoring function is the minimum tree size, is NP-hard. Furthermore, the problem of constructing an approximate ultrametric tree with approximation error ratio within $n^{epsilon}, epsilon > 0$, is also NP-hard. When the distance matrix is metric, the problem is called the triangle minimum ultrametric tree problem ($ riangle$MUT). For the $ riangle$MUT, there is a previous approximation algorithm, with error ratio $leq 1.5 ( lceil log n
ceil + 1 )$. And we shall propose an improvement, with error ratio $leq lceil log_{alpha} n
ceil + 1 cong 1.44 lceil log n
ceil + 1$, where $alpha = frac{sqrt{5}+1}{2}$ for solving the $ riangle$MUT 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 with
some fixed leaf node circular order. The time complexity of the
dynamic programming is $O(n^3)$, if the scoring function is the
minimum tree size or $L^1$-min increment.
|
Page generated in 0.0705 seconds