| dc.description.abstract | The study of phylogenetics involves the identification of evolutionary relationships between species. Perfect phylogeny is one of the classical character-based models. In this model, there are only two states for each character: zero, where the character is absent; and one, where it is present. All previous perfect phylogeny based models assume the states of the characters are discrete. However, fuzzy boundaries between species and degrees of character development are commonly found in nature. These phenomena show the need for a more relaxed model. This dissertation proposes the fuzzy (perfect) phylogeny model that extends the perfect phylogeny model to allow fuzzy memberships of the characters. In this dissertation, the fuzzy phylogeny model is studied, including its properties and algorithmic solution. Due to the fuzziness of characters, two relaxation problems for the fuzzy phylogeny are proposed, namely the Adjustment problem for Fuzzy Phylogeny (AFP problem) and the optimal AFP problem. However, the problems are proven to be NP-hard. So, two super-polynomial algorithms, namely, the BF-algorithm and the G-algorithm, are introduced to provide exact solutions to the (optimal) AFP problem. Moreover, to provide a practical solution to the (optimal) AFP problem, a sub-optimal algorithm called the H-algorithm is also introduced. Finally, future work for this research is discussed. That includes improvement on algorithms, other relaxation problems, and formulations of problems that assess the confidence of a phylogenetic tree. | |
