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
Pseudocode of the MTRT algorithm.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0103622-g011: Pseudocode of the MTRT algorithm.

Mentions: If has more triplets, then the probability of having more duplications is high. The first part of help to reduce the number of duplications and the second part of help to produce a MUL tree which is relatively balanced. Since minimizing the number of triplets is more important, we give bigger weight (2, by default) for the first part. The pseudocode of the MTRT algorithm is detailed in Figure 11.


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

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

Pseudocode of the MTRT algorithm.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0103622-g011: Pseudocode of the MTRT algorithm.
Mentions: If has more triplets, then the probability of having more duplications is high. The first part of help to reduce the number of duplications and the second part of help to produce a MUL tree which is relatively balanced. Since minimizing the number of triplets is more important, we give bigger weight (2, by default) for the first part. The pseudocode of the MTRT algorithm is detailed in Figure 11.

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