Number of rooted
bifurcating trees with t taxa
Taxonomists
sometimes ask, If you want to find the shortest tree, why
not write out all the possible trees & choose the shortest?
The answer is that it's computationally impossible. The number
of possible trees follows a hyper-exponential function as #
trees = [(2t-3)!] / 2t-2(t-2)!]. The Branch
& Bound algorithm begins to require too much computer
time to be practical at about t = 20, and very rapidly
exceeds the number of possible trees that it is possible to
represent on a single 64-bit computer, or a network of such
computers, or all computers available. With N = 52 taxa,
a relatively modest phylogenetic study, the number of possible
solutions (2.75 x 1080) exceeds Eddinger's
Number, the estimated number of molecules in the Universe
(~1080) !