Wagner Trees - SPR - TBR
From TNT
[Wagner Trees]
Except in the case of constraints, the addition sequence for wagner trees is totally randomized, except for the outgroup taxon (which is always the first taxon added). The insertion sequence of new taxa to the growing tree is (by default) not totally random: the possible locations for the new taxon are tried from the root of the tree to the tips, or from the tips to the root (which option is chosen is determined at random, for each taxon to add; both are equiprobable). In some extreme cases, this may be undesirable. If the data are entirely uninformative (e.g. a matrix with no characters) and no tree collapsing is in effect, then pectinate trees result from such insertion sequence. It is possible to randomize the insertion sequence for new taxa, so that all locations are tried in a random order. This is set with rseed[; the alternative is rseed ]; (default, up/down sequence). For large data sets, building a wagner tree with a randomized insertion sequence may actually take shorter than with the up/down sequence (that is probably because the best placement is often found somewhat in the middle of the tree, not in the tips or root; checking the tips or root first provides worse bounds to give up length calculations, for a greater portion of the time). For data with no informative characters (and with collapsing turned off), wagner trees with a random insertion sequence are (more or less) equivalent to random trees. If your data are more or less structured, setting one or the other is irrelevant.
Command: mult
Note that randomization of the insertion sequence has no effect when wagner trees are built under constraints (i.e. the insertion sequence is always up/down in this case).
[SPR and TBR]
The two types of swapper are designed to work as best as possible under diferent circumstances.
The time to complete swapping on a tree (that is, on a tree which does not lead to better trees by swapping) changes with about the square of the number of taxa for both SPR and TBR (this is true even when TBR actually “looks” at a number of rearrangements which increases with the cube of the taxa).
SPR is designed to work best at the initial stages of a search, when better trees are being found frequently; it is not as fast as it could be for trees which are already optimal or near-optimal.
TBR is designed instead to work best for large numbers of taxa, when the trees being swapped are optimal or near-optimal, that is, when better trees are not being found frequently, and also to work best on well-structured data (i.e. data where there are numerous relatively well supported groups). If the data are very poorly structured, swapping through a tree takes longer. For Källersjo et al.’s 2500-taxon matrix (1999), the time to complete TBR swappping on a near-optimal tree (running on a 800 MHz PIII machine) is about 12 secs.; PAUP* on the same machine takes over 18 minutes to complete TBR swapping on the same tree (i.e. a 90 times speed difference; PAUP* takes about 6 minutes to complete SPR on the same tree, so that completing TBR for 2500 taxa in TNT is 30 times faster than completing SPR with PAUP*).
Neither type of swapper is highly optimized for low numbers of taxa. For small data sets, expect no big differences ( i.e. no more than 5-10 times) in running times for TNT and other programs. These take no time anyway, so it seemed best to preserve an implementation focused on large data sets.
Path: Analyze/traditional search
