CAFCA - Manual

The following introduction is according to Meacham (1981, 1984). Character compatibility analysis is a technique to reveal patterns of agreement and disagreement among characters in a data matrix. Characters serve as a basis for comparing the taxa in the data matrix. Characters can have two of more states. Taxa are considered alike with respect to a character if they share the same character state. In this way a character allows the recognition of discrete classes (sets) of taxa. Accordingly, a qualitative character is defined as a set of character states, which are mutually exclusive and exhaustive subsets of the collection of terminal taxa in the data matrix. Characters in the latter sense are considered compatible if and only if there is no conflict in membership. If there is a conflict among two characters in the way they subdivide the set of terminal taxa in subsets according to their states, then these characters are considered incompatible. To put it otherwise: "Two characters are compatible if there is at least one hypothesis of evolutionary relationship (i.e. tree) that is consistent with both characters." (Estabrook and Anderson, 1978).

Characters can be tested pairwise as to their compatibility. If a character has two states, 0 and 1, two characters are compatible with each other if three or fewer of the four possible combinations of their states 00, 01, 10, and 11 occur in the data matrix. A collection of characters are mutually compatible if and only if they are all pairwise compatible; the so-called Pairwise Compatibility Theorem. This theorem has been proven for directed (= polarised = with known ancestor) and undirected two-state characters, as well as for multi-state characters which are polarised and ordered, or ordered but unpolarized (states connected in an undirected network). The proof of this theorem for unordered + unpolarized multi-state characters is still open. (Note that according to the Estabrook and Anderson [1978] definition given above two unordered unpolarized multi-state characters are compatible if both have a CI=1 for a given cladogram).

Character compatibility analysis is aimed at finding the largest sets of mutually compatible characters (or maximal clique). These sets are used to build cladograms. For each maximal clique found, characters incompatible with it are excluded from consideration. For this reason character compatibility has been severely criticised, for instance by Farris and Kluge (1979) who state that "... deletion of a character from consideration, however, does nothing to indicate which points of similarity in a character are the result of homoplasy and which are not. Specific parallelisms or reversals are not detected by such methods."

Wilkinson (1994) showed for binary data that character compatibility analysis and parsimony analysis can only differ when there are more than five terminal taxa present in the data matrix. This is so because in standard parsimony methods the number of steps that a character can contribute to the length of the cladogram, its threshold (Felsenstein, 1981) is its maximum number of steps, i.e. its steps on an unresolved cladogram or bush. The maximum number of steps of a binary character is equal to the number of taxa scored for the minority state. For five (or fewer) taxa the minority is either 1 or 2. Thus, the threshold for any character will not exceed 2. Under this condition only uniquely derived characters provide support for a cladogram, rendering standard parsimony equivalent to character compatibility analysis (Felsenstein, 1981, p 192).

In exploring the relationship between character compatibility and group (or component) compatibility I will not use the same simple example data matrix with only 5 taxa as used in earlier paragraphs, but turn to examples from the literature, for the reason outlined above.

Penny (1982) showed the incompleteness of character (in)compatibility analyses in the sense that the (in)compatibility matrix used in the computations does not preserve and contain all the information present in the original data. In general it is not possible to get back to the original data given the (in)compatibility matrix. Different characterstate distributions over taxa may all lead to the same (in)compatibility matrix for characters. Besides the criticism against character compatibility outlined by e.g. Farris and Kluge (1979) the objections as raised by Penny (1982) are rather fundamental and analogous to those raised against distance data and phenetic approaches. I will show that these objections do not hold for group (and component) compatibility. Penny (1982) used the following character compatibility matrix in his example:

1 1 0
1 1 0
0 0 1

        a    b    c    d    e    f

    w  AAA  AAA  AAA  AAA  AAA  AAA 
    x  AAB  AAB  BBA  BBB  BBA  BBB 
    y  BBA  BBB  AAB  AAB  BBB  BBA
    z  BBB  BBA  BBB  BBA  AAB  AAB 

        I    I   II   II   III  III


    w ---\  /--- y    w ---\  /--- x    w ---\  /--- x 
         |--|              |--|              |--| 
    x ---/  \--- z    y ---/  \--- z    z ---/  \--- y 
 
          I                 II               III

In CAFCA, compatibility matrices are drawn for sets of terminal taxa and not for characters. If we consider all possible sets, excluding the empty set, for the 4 taxa w, x, y, and z in Penny's example we arrive at 15 different groupings: {w}, {x}, {y}, {z}, {wx}, {wy}, {wz}, {xy}, {xz}, {wxy}, {wxz}, {wyz}, {xyz}, and {wxyz}. When we draw a square compatibility matrix for these sets and put a 1 for each pair of sets that is compatible, i.e., either in- or excludes each other but does not overlap, it is easy to see that the 6 different data sets given above, will render 3 different sets of terminal taxa and therefore 3 different compatibility matrices for sets of terminal taxa (i.e., a and b are the same, as are c - d, and e - f), whether we use PMS or SMS. CAFCA will recover cladogram type I as the MPC for data set a and b, cladogram type II as the MPC for data set c and d, and cladogram type III for data set e and f, indicating the preservation of phylogenetic (or at least cladogenetic) relevant information in its group compatibility matrix.

As I have shown earlier when explaining the CCSI as an optimality criterion, cladogram length as the sum of steps in separate characters on the particular cladogram is an a posteriori quality assessment, as are CI, RC, and RQ for that matter, only possible after cladogram optimisation. As a matter of fact, cladogram optimisation, at least the downpass in the algorithm, is the method to estimate the number of steps a character takes on a cladogram. Compatibility, on the other hand, either of characters, character states, or sets of terminal taxa, is an a priori assessment, i.e., prior to the computation of cladograms and optimisation of characters, based on primary homology assumptions.

From this point of view the contrast between parsimony methods and compatibility methods as cladogram finding tools is unbalanced. If compatibility methods could know what standard parsimony methods need to know, that is, an estimate of the character states on the inner nodes of the cladogram, assessment of compatibility, whether of characters, character states, or set membership of taxa, would benefit. Parsimony finds its base in tests of congruence among characters and character states, and the quality of the results of the analysis (cladograms) is assessed after this test. As a corollary, primary homologies have changed to secondary ones, now each on its proper level of generality. As a result characters and character states incompatible before the analysis may be compatible after interpretation of primary homologies (optimisation). Thus, as a cladogram finding tool, compatibility based on primary homologies can never hope to find what may be the case for secondary homologies, unless all possible secondary homologies are in one way or another considered as data in the search for cladograms. Compatibility and parsimony methods would be on the same footing if, during computations, the compatibility assessments could change during and as a result of optimisation, just as the estimate of the number of steps may change as a result of different optimisations.

The problem for compatibility methods for character data is, then, how to incorporate effectively and efficiently all possible secondary homologies if it wants to find all MPC's. For indirect data, as in historical biogeography and cases of co-evolution, the situation is different as we will see in chapter 6.

As the next examples from the literature may show in exploring the relationship between character compatibility and group compatibility, the use of strict monothetic sets, or all possible additive binary codings, or three-taxon statement permutations, etc.., can serve as approximations to the consideration of all possible secondary homologies.

Questions ?:  

© M. Zandee 1996.