Return to search

Approximation Algorithms for Constructing Evolutionary Trees

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0810101-223823
Date10 August 2001
CreatorsHuang, Chia-Mao
ContributorsD. J. Guan, B. Y. Wu, S. C. Tai, Chang-Biau Yang
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0810101-223823
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.0021 seconds