Warning: the cladistics package in PAST is fully operational, but lacking in comprehensive functionality. The PAST cladistics package is adequate for education and initial data exploration, but for more serious work we recommend a specialized program for systematics (Paup, TNT etc.).
The module requires a character matrix with taxa in rows, outgroup in first row.
Algorithms are from Kitching et al. (1998) and Felsenstein (2004).
Character states should be coded using integers in the range 0 to 255, or with the letters c, a, g, t, u (upper or lower case). The first taxon is treated as the outgroup, and will be placed at the root of the tree.
Missing values are coded with a question mark (?). Please note that PAST does not collapse zero-length branches. Because of this, missing values can lead to a proliferation of equally shortest trees ad nauseam, many of which are in fact equivalent.
Algorithms
There are four algorithms available for finding short trees:
Exhaustive
The exhaustive algorithm evaluates all possible trees. Like the branch-and-bound algorithm it will necessarily find all shortest trees, but it is very slow. The maximum number of taxa allowed for exhaustive search is 12, for which more than 600 million trees are evaluated. The only advantage over branch-and-bound is the plotting of tree length distribution. This histogram may indicate the quality of your matrix, in the sense that there should be a tail to the left such that few short trees are isolated from the greater mass of longer trees (but see Kitching et al. 1998 for critical comments on this).
Branch-and-bound
The branch-and-bound algorithm is guaranteed to find all shortest trees. The total number of shortest trees is reported, but a maximum of 10000 trees are saved. The branch-and-bound algorithm can be very time consuming for data sets with more than 16 taxa.
Heuristic, nearest neighbour interchange
This heuristic algorithm adds taxa sequentially in the order they are given in the matrix, to the branch where they will give least increase in tree length. After each taxon is added, all nearest neighbour trees are swapped to try to find an even shorter tree.
Like all heuristic searches, this one is much faster than the algorithms above and can be used for large numbers of taxa, but is not guaranteed to find all or any of the most parsimonious trees. To decrease the likelihood of ending up on a suboptimal local minimum, a number of reorderings can be specified. For each reordering, the order of input taxa will be randomly permutated and another heuristic search attempted.
Please note: Because of the random reordering, the trees found by the heuristic searches will normally be different each time. To reproduce a search exactly, you will have to start the parsimony module again from the menu, using the same value for Random seed. This will reset the random number generator to the seed value.
Heuristic, subtree pruning and regrafting
This algorithm (SPR) is similar to the one above (NNI), but with a more elaborate branch swapping scheme: A subtree is cut off the tree, and regrafting onto all other branches in the tree is attempted in order to find a shorter tree. This is done after each taxon has been added, and for all possible subtrees. While slower than NNI, SPR will often find shorter trees.
Heuristic, tree bisection and reconnection
This algorithm (TBR) is similar to the one above (SPR), but with an even more complete branch swapping scheme. The tree is divided into two parts, and these are reconnected through every possible pair of branches in order to find a shorter tree. This is done after each taxon is added, and for all possible divisions of the tree. TBR will often find shorter trees than SPR and NNI, at the cost of longer computation time.
Character types
Unordered
Characters are reversible and unordered, meaning that all changes have equal cost. This is the criterion with fewest assumptions, and is therefore generally preferable.
Ordered
Characters are reversible and ordered, meaning that 0->2 costs more than 0->1, but has the same cost as 2->0.
Bootstrap
Bootstrapping is performed when the Bootstrap replicates value is set to non-zero. The specified number of replicates (typically 100 or even 1000) of your character matrix are made, each with randomly weighted characters. The bootstrap value for a group is the percentage of replicates supporting that group. A replicate supports the group if the group exists in the majority rule consensus tree of the shortest trees made from the replicate.
Warning: Specifying 1000 bootstrap replicates will clearly give a thousand times longer computation time than no bootstrap! Exhaustive search with bootstrapping is unrealistic and is not allowed.
Cladogram plotting
All shortest (most parsimonious) trees can be viewed, up to a maximum of 10000 trees. If bootstrapping has been performed, a bootstrap value is given at the root of the subtree specifying each group.
Character states can also be plotted onto the tree, as selected by the Character menu. This character reconstruction is unique only in the absence of homoplasy. In case of homoplasy, character changes are placed as close to the root as possible, favouring one-time acquisition and later reversal of a character state over several independent gains (so-called accelerated transformation).
The Phylogram option allows plotting of trees where the length of vertical lines (joining clades) is proportional to branch length.
Consistency index
The per-character consistency index (ci) is defined as m/s, where m is the minimum possible number of character changes (steps) on any tree, and s is the actual number of steps on the current tree. This index hence varies from one (no homoplasy) and down towards zero (a lot of homoplasy). The ensemble consistency index CI is a similar index summed over all characters.
Retention index
The per-character retention index (ri) is defined as (g-s)/(g-m), where m and s are as for the consistency index, while g is the maximal number of steps for the character on any cladogram (Farris 1989). The retention index measures the amount of synapomorphy on the tree, and varies from 0 to 1.
Please note that in the present version, the retention index is only correctly calculated when using unordered characters.
Consensus tree
The consensus tree of all shortest (most parsimonious) trees can also be viewed. Two consensus rules are implemented: Strict (groups must be supported by all trees) and majority (groups must be supported by more than 50% of the trees).
Bremer support (decay index)
The Bremer support for a clade is the number of extra steps you need to construct a tree (consistent with the characters) where that clade is no longer present. There are reasons to prefer this index rather than the bootstrap value. PAST does not compute Bremer supports directly, but for smaller data sets it can be done manually as follows:
- Perform parsimony analysis with exhaustive search or branch-and-bound. Take note of the clades and the length N of the shortest tree(s) (for example 42). If there are more than one shortest tree, look at the strict consensus tree. Clades which are no longer found in the consensus tree have a Bremer support value of 0.
- In the box for Longest tree kept, enter the number N+1 (43 in our example) and perform a new search.
- Additional clades which are no longer found in the strict consensus tree have a Bremer support value of 1.
- For Longest tree kept, enter the number N+2 (44) and perform a new search. Clades which now disappear in the consensus tree have a Bremer support value of 2.
- Continue until all clades have disappeared.
References
Farris, J.S. 1989. The retention index and the rescaled consistency index. Cladistics 5:417-419.
Felsenstein, J. 2004. Inferring phylogenies. Sinauer Associates.
Kitching, I.J., P.L. Forey, C.J. Humphries & D.M. Williams. 1998. Cladistics. Oxford University Press.