Limits...
An experimental study of Quartets MaxCut and other supertree methods.

Swenson MS, Suri R, Linder CR, Warnow T - Algorithms Mol Biol (2011)

Bottom Line: We also observed that taxon sampling impacted supertree accuracy, with poor results obtained when all of the source trees were only sparsely sampled.Our results show that supertree methods that improve upon MRP are possible, and that an effort should be made to produce scalable and robust implementations of the most accurate supertree methods.Finally, since supertree topological error is only weakly correlated with the supertree's topological distance to its source trees, development and testing of supertree methods presents methodological challenges.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, The University of Texas at Austin, Austin TX, USA. mswenson@cs.utexas.edu.

ABSTRACT

Background: Supertree methods represent one of the major ways by which the Tree of Life can be estimated, but despite many recent algorithmic innovations, matrix representation with parsimony (MRP) remains the main algorithmic supertree method.

Results: We evaluated the performance of several supertree methods based upon the Quartets MaxCut (QMC) method of Snir and Rao and showed that two of these methods usually outperform MRP and five other supertree methods that we studied, under many realistic model conditions. However, the QMC-based methods have scalability issues that may limit their utility on large datasets. We also observed that taxon sampling impacted supertree accuracy, with poor results obtained when all of the source trees were only sparsely sampled. Finally, we showed that the popular optimality criterion of minimizing the total topological distance of the supertree to the source trees is only weakly correlated with supertree topological accuracy. Therefore evaluating supertree methods on biological datasets is problematic.

Conclusions: Our results show that supertree methods that improve upon MRP are possible, and that an effort should be made to produce scalable and robust implementations of the most accurate supertree methods. Also, because topological accuracy depends upon taxon sampling strategies, attempts to construct very large phylogenetic trees using supertree methods should consider the selection of source tree datasets, as well as supertree methods. Finally, since supertree topological error is only weakly correlated with the supertree's topological distance to its source trees, development and testing of supertree methods presents methodological challenges.

No MeSH data available.


Scaffold density vs. QMC-based and MRP running times. Running times (in seconds) of QMC supertree methods and gMRP on mixed datasets; the y-axis is given with a logarithmic scale.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: Scaffold density vs. QMC-based and MRP running times. Running times (in seconds) of QMC supertree methods and gMRP on mixed datasets; the y-axis is given with a logarithmic scale.

Mentions: We compared the running time of all supertree methods on simulated data. Figure 5 gives the results for the QMC variants and gMRP, and Figure 6 gives results for gMRP, QMC(Exp+TSQ), and the other (non-QMC-based) supertree methods.


An experimental study of Quartets MaxCut and other supertree methods.

Swenson MS, Suri R, Linder CR, Warnow T - Algorithms Mol Biol (2011)

Scaffold density vs. QMC-based and MRP running times. Running times (in seconds) of QMC supertree methods and gMRP on mixed datasets; the y-axis is given with a logarithmic scale.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: Scaffold density vs. QMC-based and MRP running times. Running times (in seconds) of QMC supertree methods and gMRP on mixed datasets; the y-axis is given with a logarithmic scale.
Mentions: We compared the running time of all supertree methods on simulated data. Figure 5 gives the results for the QMC variants and gMRP, and Figure 6 gives results for gMRP, QMC(Exp+TSQ), and the other (non-QMC-based) supertree methods.

Bottom Line: We also observed that taxon sampling impacted supertree accuracy, with poor results obtained when all of the source trees were only sparsely sampled.Our results show that supertree methods that improve upon MRP are possible, and that an effort should be made to produce scalable and robust implementations of the most accurate supertree methods.Finally, since supertree topological error is only weakly correlated with the supertree's topological distance to its source trees, development and testing of supertree methods presents methodological challenges.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, The University of Texas at Austin, Austin TX, USA. mswenson@cs.utexas.edu.

ABSTRACT

Background: Supertree methods represent one of the major ways by which the Tree of Life can be estimated, but despite many recent algorithmic innovations, matrix representation with parsimony (MRP) remains the main algorithmic supertree method.

Results: We evaluated the performance of several supertree methods based upon the Quartets MaxCut (QMC) method of Snir and Rao and showed that two of these methods usually outperform MRP and five other supertree methods that we studied, under many realistic model conditions. However, the QMC-based methods have scalability issues that may limit their utility on large datasets. We also observed that taxon sampling impacted supertree accuracy, with poor results obtained when all of the source trees were only sparsely sampled. Finally, we showed that the popular optimality criterion of minimizing the total topological distance of the supertree to the source trees is only weakly correlated with supertree topological accuracy. Therefore evaluating supertree methods on biological datasets is problematic.

Conclusions: Our results show that supertree methods that improve upon MRP are possible, and that an effort should be made to produce scalable and robust implementations of the most accurate supertree methods. Also, because topological accuracy depends upon taxon sampling strategies, attempts to construct very large phylogenetic trees using supertree methods should consider the selection of source tree datasets, as well as supertree methods. Finally, since supertree topological error is only weakly correlated with the supertree's topological distance to its source trees, development and testing of supertree methods presents methodological challenges.

No MeSH data available.