Testing character correlation using pairwise comparisons on a phylogeny

In comparative biology, pairwise comparisons of species or genes (terminal taxa) are used to detect character associations. For instance, if pairs of species contrasting in the state of a particular character are examined, the member of a pair with a particular state might be more likely than the other member to show a particular state in a second character. Pairs are chosen so as to be phylogenetically separate, that is, the path between members of a pair, along the branches of the tree, does not touch the path of any other pair. On a given phylogenetic tree, pairs must be chosen carefully to achieve the maximum possible number of pairs while maintaining phylogenetic separation. Many alternative sets of pairs may have this maximum number. Algorithms are developed that find all taxon pairings that maximize the number of pairs without constraint, or with the constraint that members of each pair have contrasting states in a binary character, or that they have contrasting states in two binary characters. The comparisons chosen by these algorithms, although phylogenetically separate on the tree, are not necessarily statistically independent.