Content
Summary
Reconstructing true evolutionary history is computationally difficult because the number of potential phylogenetic tree topologies grows exponentially with the number of taxa. To manage this complexity, researchers calculate unrooted trees first and then root them using an outgroup, while carefully selecting molecular markers and evolutionary models. This approach reduces the initial computational burden before applying the final rooting step.
Intuition
Imagine trying to find the one correct family tree among millions of possibilities just by looking at ten relatives. The challenge in molecular phylogenetics is that the search space for correct tree topologies becomes enormously large even with a moderate number of taxa. This increase follows an exponential function, meaning the computational demand rises drastically as more sequences are added. For instance, while three taxa have only one unrooted and three rooted possibilities, ten taxa result in over two million unrooted and thirty-four million rooted topologies. This explosive increase makes finding the true tree computationally very demanding when the number of sequences is large. To simplify this, we first find the unrooted structure, which has fewer possibilities, and then use external information to determine the direction of evolution.
Key equations
The number of rooted tree topologies (N_R) for n taxa.
The number of unrooted tree topologies (N_U) for n taxa.
Derivation
- The number of possible topologies is determined by specific factorial formulas depending on whether the tree is rooted or unrooted.
- For rooted trees with n taxa, the number of topologies (N_R) is calculated as (2n-3)! / 2^{n-2}(n-2)!.
- For unrooted trees, the count (N_U) is given by (2n-5)! / 2^{n-3}(n-3)!.
- The factorial notation (2n-3)! represents the product of positive integers from 1 to 2n-3.
- As an example, for six taxa, there are 105 unrooted trees and 945 rooted trees.
- Because the number of rooted topologies is significantly larger than that of unrooted ones, the search for a true phylogenetic tree can be simplified by calculating unrooted trees first.
- Once an optimal unrooted tree is identified, it can be rooted by designating specific taxa as an outgroup based on external information.
Worked example
Calculate the number of unrooted tree topologies for six taxa and explain why this approach simplifies the search compared to rooted trees.
- Identify the number of taxa, n = 6.
- Use the unrooted tree formula: N_U = (2n-5)! / 2^{n-3}(n-3)!.
- Substitute n=6: N_U = (12-5)! / 2^{6-3}(6-3)! = 7! / 2^3 * 3!.
- Calculate 7! = 5040, 2^3 = 8, and 3! = 6.
- N_U = 5040 / (8 * 6) = 5040 / 48 = 105.
- The source states that for six taxa, there are 945 rooted trees. Since 105 is significantly fewer than 945, searching the unrooted space first reduces the computational burden.
Answer There are 105 unrooted tree topologies for six taxa. This simplifies the search because there are fewer unrooted topologies (105) than rooted ones (945), allowing researchers to find the optimal unrooted structure before applying the rooting step.
Common mistakes
- Students might confuse the formulas for rooted and unrooted trees; note that the rooted formula uses (2n-3)! while the unrooted uses (2n-5)!.
- It is important to distinguish between strict consensus (all conflicting nodes collapsed) and majority rule (only nodes with >50% agreement retained).
- The factorial term (2n-3)! is not just 2n-3 but the product of all integers from 1 to 2n-3.