Hunting for trees in binary character sets: efficient algorithms for extraction, enumeration, and optimization.

We describe a useful and efficient tree building technique that is closely related to the maximum compatible subset method. Given a set of binary characters C and a degree bound d, the algorithm we describe counts the number of trees T that satisfy (1) the edges of T correspond to characters contained in C, and (2) the vertices of T have degree bounded by d. If the characters are weighted then we can efficiently determine which of these trees have maximum summed edge weight, where the weight of an edge equals the weight of the corresponding binary character in C. The complexity of the algorithms equals O(nk + ndK(d-1), where n is the number of taxa, k is the number of characters, and K is the number of distinct characters. A number of new tree consensus methods based on the algorithm are introduced, including one that uses edge weighted trees. As well, we illustrate the applicability of the algorithm for large sequence data sets by analyzing sequences from the "Out of Africa" mtDNA data set.