Unrooted trees

Both Cayley and Polya were able to enumerate unrooted trees and C-trees, but the methods they used were somewhat involved. A significant improvement in the enumeration of these trees, also known as "free" trees, was made by Otter [OttR48]. Otter s method depends on the concept of a dissimilarity characteristic, and deserves a brief description. 

The enumeration result that we want is obtained by summing the equation of the theorem over all unrooted trees with a given number p of vertices. Thus we have... 

Further progress in asymptotic tree enumeration was made by Otter, who in [OttR48] considered the problem of rooted and unrooted trees with maximum degree m. Having enumerated unrooted trees by the method already described, he proceeded to derive asymptotic estimates, and after ten pages of analysis arrived at a number of results, of which the following is typical ... 

The unrooted tree was generated using the program Phylo Draw. 

Fig. 5. An unrooted tree of the seven globins. The tree in Fig. 1 was obtained by placing the root at the arrow.

If there are only two sequences, then, there is only one possible rooted or unrooted tree if branch lengths are ignored and focus is on the tree... 

Fig. 6. The three possible rooted and the single unrooted tree for three sequences (top) and the three unrooted trees for four sequences (bottom).

Fig. 8. The three possible unrooted trees for four sequences and the arrangement of residues at the column in the alignment in each. Tree A requires one (or more) steps to explain it (either a to g or a g to a change), and trees B and C require two steps (at least) each.

Fig. 9. The unrooted tree top) shows unequal rates of evolution along the terminal branches. Applying the UPGMA method to the underlying sequences results in the tree at the bottom, which incorrectly joins sequences 2 and 4.

Within the NiFe(Se) hydrogenase family, the unrooted tree (Fig. 2.4) clearly reveals several major lineages. As might be expected, the enzyme groups discussed above all emerge as distinct clades which reflect the major prokaryotic groups and the enzyme... 

Fig. 11.2. Neighbour-joining phylogenetic tree of the predicted peroxiredoxins shown in Fig. 11.1. This unrooted tree was generated using the computer program PHYLIP (Felsenstein, 1989) version 3.5c. GenBank accession s of the sequences used in this analysis are shown in Fig. 11.1 legend.

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... 

Drawing Draw/Tree DNA/Protein Plot unrooted tree... 

Fig. 2.14 Reconstructed phylogeny of four types of dyp peroxidases. The unrooted tree obtained from the NJ method of the MEGA package [13] is presented. A very similar tree was obtained...

The six aligned sequences in Fig. 1 were used to build amino add parsimony trees by PROTPARS in PAUP.13 An exhaustive search of the 105 alternative unrooted trees was performed the resulting distribution of possible trees was skewed14 positively, with a long tail (not shown) containing the shortest tree. This shortest unrooted tree (Fig. 2) requires 601 amino acid replacements the next shortest tree requires 625 events. In this case, the most parsimonious tree appears rather trustworthy. 

---