Unrooted topologies

The cladistic parsimony principle, as understood by most users of computer programs, is utilized only in the search for the shortest tree. I have frequently heard cladists say that it should be impossible to discover an optimal tree topology by hand when many species are being considered, because there are millions of alternative topologies to be considered (e.g., about two million unrooted topologies for only 10 terminal taxa). As there exist more than 900,000 known species of insects and the number of alternative topologies that... 

Hennig did not try to construct tree-like diagrams with unordered or unpolarized characters. Unrooted topologies do not show the evolution of characters, but they may contain partitions of taxa that reflect real shared properties of organisms and therefore are informative. 

Blackwelder s commitment to, 43 Committee on Zoological Nomenclature, 26 Mayr s complaint about, 33 Universal laws, problem of induction and, 61 Universal statements, 62, 64 Unrooted topologies, 106 USNM, see United States National Museum... 

An arbitrary endpoint can also be marked as "root". A tree with a root will be called a planted tree the vertices different from the root are nodes. If no root is marked, the tree is called an unrooted or free tree. From a topological point of view, two trees with the same structure are identical the exact definition of this and some similar, less familiar notions, will be discussed in Sections 34-35. In the sequel, we use the following notations ... 

Fig. 1. Unrooted phylogenetic tree based on the core amino acid sequences of 113 catalases. The numbers at the three main nodes represent the proportion (out of 100) of bootstrap sampling that supports the topology. The three main clades are circled for clarity.

The number of possible tree topologies rapidly increases with an increase in the number (N) of OTUs. The general equation (Miyamoto and Cracroft, 1991) for the possible number of topologies for bifurcating unrooted trees (TN) with n (>3) OTUs (taxa) is given by... 

Variations of two exact algorithms (algorithms that will always find the optimal solution) are commonly used. The first is to search exhaustively through all possible tree topologies for the best solution(s). This method is computationally simple for 9 or fewer taxa (for which there are 135,135 labeled, unrooted, bifurcating trees) and is only moderately time-consuming for 10 or 11 taxa (2,027,025 and 34,459,425 trees, respectively).2 For 12 taxa, the evaluation becomes laborious (654,729,075 trees), and for 13 or more taxa (a 13,749,310,575 trees) the calculations are usually impractical. The chief advantages of exhaustive searches are (1) the optimal tree(s) is always found and (2) all other possibilities can be ranked with respect to the optimal solution(s). 

---