Computational Complexity

This hole-punch cloud above the Stanford Oval is not a tree, but it does provide an opportunity to discuss the computational complexity of phylogenetic analysis. The number of possible bifurcating phylogenetic tree topologies grows extremely rapidly — faster than exponentially, with the formula \( (1)(3)(5)…(2n-3) \) for \(n\) species. With 10 species, the number of trees is 34,459,425. Enumerations of classes of trees are helpful in understanding the sets of objects that represent possible evolutionary outcomes, and because of this rapid increase in the number of trees, algorithms for phylogenetic inference must be attentive to challenges in computation.