Counting Ancestral Reconstructions in a Fixed Phylogeny

摘要

We give formulas for calculating in polynomial time the number of ancestral reconstructions for a tree with binary leaf- and root labels for each number of 0 ®rightarrow 1 and 1 ®rightarrow 0 arcs. For trees of fixed degree, the corresponding numbers of 0 ®rightarrow 0 and 1 ®rightarrow 1 arcs can be deduced. We calculate intervals for the relative cost of 0 ®rightarrow 1 and 1 ®rightarrow 0 transitions over which the same labelings remain the cheapest.