Cipres Web Portal

Rec-I-DCM3 (Recursive Iterative Disk Covering Method3) is one of a family of Disk Covering Methods to speed the inference of phylogenetic trees from large data sets. Rec-I-DCM3 is currently available on the CIPRES cluster to speed analyses of large-scale problems using PAUP or RAxML as the inference engine.

Estimations of phylogenetic trees are often obtained through the use of heuristics for maximum parsimony (MP) and maximum likelihood (ML); both of which are NP-hard problems. Although apparently good heuristics have been devised, even these fail to produce good solutions in reasonable time for large datasets. The practical limit today is probably less than one thousand sequences; reconstructing much larger trees remains a Grand Challenge problem. Rec-I-DCM3 is a promising new divide-and-conquer technique, one of a whole family of Disk-Covering Methods (DCMs) that operate by iteratively dividing the input set of sequences into smaller overlapping subproblems, solving them using some base method (e.g., neighbor-joining, heuristic MP, heuristic ML, etc.), and then merging these subtrees into a single, phylogenetic tree. All DCMs boost the performance of the base method. The method available here is composed of a new DCM algorithm, which we call DCM3, but utilizes recursion and iteration as well, hence the name Rec-I-DCM3. As assembled here, Rec-I-DCM3 boosts phylogenetic reconstruction methods that can produce dramatic improvements in speed for standard heuristics, as well as substantial improvements over the very best methods (which are harder to improve). We demonstrate the power of this new DCM on ten large biological datasets ranging from 1,322 to 13,921 sequences.

Rec-I-DCM3 can also be accessed at the original CIPRES-Portal or as part of the CIPRES software distribution.

Rec-I-DCM3 home page here.

INPUT = the input is a Nexus file containing a protein or nucleic acid matrix.

Test input file (nucleic acid): rid3-paup_infile.nex

Test intermediate results file: rid3-paup_intermediateresults.nex

Test output file: rid3-paup_results.nex

If you use Rec-I-DCM3, please cite: Roshan, U., Moret, B. M. E., Williams, T. L., Warnow, T.(2004) Rec-I-DCM3: A Fast Algorithmic Technique for Reconstructing Large Phylogenetic Trees, Proceedings of the IEEE Computational Systems Bioinformatics conference (CSB) [pdf].

If there is a tool or a feature you need, you can add it yourself or let us know.