Do triplets have enough information to construct the multi-labeled phylogenetic tree?
Bottom Line:
In this paper, we show that the SMRT does not seem to be an appropriate solution from the biological point of view.The results of MTRT show that triplets alone cannot provide enough information to infer the true MUL tree.Finally, we introduce some new problems which are more suitable from the biological point of view.
View Article:
PubMed Central - PubMed
Affiliation: Department of Mathematics, Shahid Beheshti University, G.C., Tehran, Iran.
ABSTRACT
Show MeSH
The evolutionary history of certain species such as polyploids are modeled by a generalization of phylogenetic trees called multi-labeled 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 NP-hard. There is one algorithm for the SMRT problem which is exact and runs in O(7n) 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. |
Related In:
Results -
Collection
License getmorefigures.php?uid=PMC4117514&req=5
Mentions: Using the new rooted triplet distance defined in Def. 2, the distance between MUL trees and shown in Figure 7 equals . Note that a MUL tree is not uniquely defined by its multiset of triplets. For example, two MUL trees shown in Figure 9 have the same multiset of triplets. However, it seems that for most of the MUL trees specially for large MUL trees, it is true that two MUL trees are isomorphic if they have new triplet distance equal to 0. To show this, we computed the triplet distance and new triplet distance for all simulated and real datasets. The results of simulated datasets are shown in Table 1. Suppose is a MUL tree and is the result of applying MTRT algorithm on . We define . We classify the simulated datasets into 5 classes: |
View Article: PubMed Central - PubMed
Affiliation: Department of Mathematics, Shahid Beheshti University, G.C., Tehran, Iran.