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 different "base methods". Disk-covering methods have been used with distance-based methods (like

neighbor joining In bioinformatics, neighbor joining is a bottom-up (agglomerative) clustering method for the creation of phylogenetic trees, created by Naruya Saitou and Masatoshi Nei in 1987. Usually based on DNA or protein sequence data, the algorithm require ...

) to produce "fast-converging methods", which are methods that will reconstruct the true tree from sequences that have at most a polynomial number of sites. A disk-covering method has four steps: # Decomposition: Compute a decomposition of the dataset into overlapping subsets. # Solution: Construct trees on the subsets using a base method. # Merge: Use a supertree method to merge the trees on the subsets into a tree on the full dataset. # 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. The major use of any disk-covering method is that of the "Rec-I-DCM3" disk-covering method, which has been used to speed-up

maximum likelihood In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed sta ...

and

maximum parsimony In phylogenetics, maximum parsimony is an optimality criterion under which the phylogenetic tree that minimizes the total number of character-state changes (or miminizes the cost of differentially weighted character-state changes) is preferred. ...

analyses, and are available through the NSF-funded CIPRES project (www.phylo.org). However, disk-covering methods have also been used for estimating evolutionary trees from gene order data * 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.

References

Further reading