Limits...
Do triplets have enough information to construct the multi-labeled phylogenetic tree?

Hassanzadeh R, Eslahchi C, Sung WK - PLoS ONE (2014)

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
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.

Show MeSH
Two different MUL trees with tha same multiset of triplets .
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4117514&req=5

pone-0103622-g009: Two different MUL trees with tha same multiset of triplets .

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:


Do triplets have enough information to construct the multi-labeled phylogenetic tree?

Hassanzadeh R, Eslahchi C, Sung WK - PLoS ONE (2014)

Two different MUL trees with tha same multiset of triplets .
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4117514&req=5

pone-0103622-g009: Two different MUL trees with tha same multiset of triplets .
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:

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
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.

Show MeSH