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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0810101-223823 |
| Date | 10 August 2001 |
| Creators | Huang, Chia-Mao |
| Contributors | D. J. Guan, B. Y. Wu, S. C. Tai, Chang-Biau Yang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0810101-223823 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0021 seconds