On divide-and-conquer strategies for parsimony analysis of large data sets: rec-i-dcm3 vs. TNT

GOLOBOFF, PABLO; POL, DIEGO

SYSTEMATIC BIOLOGY

Taylor and Francis

Año: 2007 vol. 56 p. 485 - 495

1063-5157

Abstract.--- Roshan et al. recently described a "divide-and-conquer" technique for parsimony analysis of large data sets, rec-i-dcm3, and stated that it compares very favorably to results using the program TNT. Their technique is based on selecting subsets of taxa to create reduced data sets or subproblems, finding most parsimonious trees for each reduced data set, recombining all parts together, and then performing global TBR swapping on the combined tree. Here, we contrast this approach to sectorial searches, which is the divide-and-conquer algorithm implemented in TNT.  This algorithm also uses a guide tree to create subproblems, with the first-pass state sets of the nodes that join the selected sectors with the rest of the topology; this allows exact length calculations for the entire topology (that is, any solution N steps shorter than the original, for the reduced subproblem, must also be N steps shorter for the entire topology). We show here that, for sectors of similar size analyzed with similar search algorithms, subdividing data sets with sectorial searches produces better results than subdividing with rec-i-dcm3. Roshan et al.'s claim that rec-i-dcm3 outperforms the techniques in TNT was caused by a poor experimental design and algorithmic settings used for the runs in TNT. In particular, for finding trees at or very close to the minimum known length of the analyzed datasets, TNT clearly outperforms rec-i-dcm3. Finally, we show that the performance of rec-i-dcm3 is bound by the efficiency of TBR implementation for the complete dataset, as this method behaves (after some number of iterations) as a technique for cyclic perturbations and improvements more than as a divide-and-conquer strategy.