“School of Biological”
Back to Papers HomeBack to Papers of School of Biological
Paper IPM / Biological / 13468  


Abstract:  
The evolutionary history of certain species such as polyploids are modeled by a
generalization of phylogenetic trees called multilabeled phylogenetic trees, or MUL
trees for short. One problem that relates to inferring a MUL tree is how to construct the
smallest possible MUL tree that is consistent with a given set of rooted triplets, or
SMRT problem for short. This problem is NPhard. There is one algorithm for the
SMRT problem which is exact and runs in O(7^{n}) time, where n is the number of
taxa. In this paper, we show that the SMRT does not seem to be an appropriate
solution from the biological point of view. Indeed, we present a heuristic algorithm
named MTRT for this problem and execute it on some real and simulated datasets.
The results of MTRT show that triplets alone cannot provide enough information to
infer the true MUL tree. So, it is inappropriate to infer a MUL tree using triplet
information alone and considering the minimum number of duplications. Finally, we
introduce some new problems which are more suitable from the biological point of
view.
Download TeX format 

back to top 