The computational challenge for reconstruction of phylogenies
Maximum parsimony and maximum likelihood require us to
consider all possible trees. Given n species, there are
(2n-3)!/[2n-2(n-2)!] distinct possible (rooted) trees for
depicting the phylogenetic relationship between these
species. For n = 10, this number is 34,459,425;
for n = 15 it is already equal to 213,458,046,676,875,
for n = 21 we get half a mole of trees.
Again, we are confronted with a problem whose most
obvious solution requires exponential running time.