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. [ABSTRACT FROM AUTHOR]