Page 218 - Applied Probability

10. Molecular Phylogeny
204
root

1 2
FIGURE 10.1. The Only Rooted Tree for Two Contemporary Taxa

the tree or speciation events (internal nodes) from which two new taxa
bifurcate.
The first theoretically interesting question about evolutionary trees is
how many trees T n there are for n contemporary taxa. For n = 2, obviously
T n = 1; the single tree with two contemporary taxa is depicted in Figure
10.1. The three possible trees for three contemporary taxa are depicted
(2n−3)!
in Figure 10.2. In general, T n = . Thus, T 4 = 15, T 5 = 105,
2 n−2 (n−2)!
T 6 = 945, and so forth.

root root root

1 2 3 1 2 3 1 3 2

FIGURE 10.2. The Three Rooted Trees for Three Contemporary Taxa

To verify the formula for T n , first note that an evolutionary tree with n
tips has 2n − 1 nodes and 2n − 2 edges. This is certainly true for n =2,
and it follows inductively because every new tip to the tree adds two nodes
and two edges. The formula for T n is proved in similar inductive fashion.
T 2 =(2 · 2 − 3)!/(2 2−2 0!) = 1 obviously works. Given a tree with n tips, tip
n + 1 can be attached to any one of the existing 2n − 2 edges or it can be
attached directly to the root if the current bifurcation of the root is moved
slightly forward in time. Thus,

T n+1 =(2n − 1)T n
(2n − 1)(2n − 3)!
=
2 n−2 (n − 2)!