Bias in tree searches and its consequences for measuring group supports

When doing a bootstrap analysis with a single tree saved per pseudoreplicate, biased search algorithms may influence support values more than actual properties of the data set. Two methods commonly used for finding phylogenetic trees consist of randomizing the input order of species in multiple addition sequences followed by branch swapping, or using random trees as the starting point for branch swapping. The randomness inherent to such methods is assumed to eliminate any consistent preferences for some trees or unsupported groups of taxa, but both methods can be significantly biased. In the case of trees created by sequentially adding taxa, a bias may occur even if every addition sequence is equiprobable, and if one of the equally optimal positions for each terminal to add to the tree is selected equiprobably. In the case of branch swapping, the bias can happen even when branch swapping equiprobably selects any of the trees of better score in the subtree-pruning-regrafting-neighborhood or tree-bisection-reconnection-neighborhood. Consequently, when the data set is ambiguous, both random-addition sequences and branch swapping from random trees may (i) find some of the optimal trees much more frequently than others and (ii) find some groups with a frequency that differs from their frequency among all optimal trees. When the data set defines a single optimal tree, the groups present in that tree may have a different probability of being found by a search, even if supported by equal amounts of evidence. This may happen in both parsimony and maximum-likelihood analyses, and even in small data sets without incongruence.