Disk-covering method

From Wikipedia, the free encyclopedia

A disk-covering method is a divide-and-conquer meta-technique for large-scale phylogenetic analysis which has been shown to improve the performance of both heuristics for NP-hard optimization problems and polynomial-time distance-based methods. Disk-covering methods are a meta-technique in that they have flexibility in several areas, depending on the performance metrics that are being optimized for the base method. Such metrics can be efficiency, accuracy, or sequence length requirements for statistical performance. There have been several disk-covering methods developed, which have been applied to base methods such as neighbor-joining and maximum parsimony.

A disk-covering method has four steps:

1. Decomposition: Compute a decomposition of the dataset into overlapping subsets.
2. Solution: Construct trees on the subsets using a base method.
3. Merge: Use a supertree method to merge the trees on the subsets into a tree on the full dataset.
4. Refinement: If the tree obtained in the merge is not fully resolved, then resolve it further into a binary tree so that it optimizes some desired objective criterion.

[edit] References

• D. Huson, S. Nettles and T. Warnow. (1999). Disk-covering, a fast-converging method for phylogenetic tree reconstruction. Journal of Computational Biology, 6:369-386.
• D. Huson, L. Vawter and T. Warnow. (1999). Solving large scale phylogenetic problems using DCM2. In Proc. 7th Int'l Conf. on Intelligent Systems for Molecular Biology (ISMB '99), pp. 118-129, AAAI Press.
• L. Nakhleh, U. Roshan, K. St. John, J. Sun and T. Warnow. (2001). Designing fast converging phylogenetic methods. In Proc. 9th Int'l Conf. on Intelligent Systems for Molecular Bioology (ISMB '01), volume 17 of Bioinformatics, pp S190-S198. Oxford U. Press.
• U. Roshan, B.M.E. Moret, T. Warnow and T.L. Williams. (2004). Rec-I-DCM3: a fast algorithmic technique for reconstructing large phylogenetic trees. In Proceedings of the IEEE Computational Systems Bioinformatics conference (CSB), Stanford, California, USA.
• J. Tang and B. Moret. (2003). Scaling up accurate phylogenetic reconstruction from gene-order data. In Proc. 11th Int'l Conf. on Intelligent Systems for Molecular Biology ISMB '03, volume 19 (Suppl. 1) of Bioinformatics, pp i305 - i312.
• T. Warnow, B. Moret and K. St. John.. (2001). Absolute convergence: True trees from short sequences. In Proc. 12th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA '01), pp. 186-195. SIAM Press, 2001.