gives an algorithm to construct the “traditional perfect phylogeny" [**T**]{}’ in linear time. Constructing [**T**]{} from [**T**]{}’ is straightforward since all we need is to incorporate the sampling information and add leaf nodes if a haplotype is observed at multiple sampling times. If we drew ${\textbf{T}}'$ from the data in Figure \[perfect\_phylo\], it would not have node $V_4$, but only a single node $V_3$ labeled by haplotype $h_C$. A description of the algorithm can be found in the supplementary material.

Likelihood
----------

The crucial step needed to compute the likelihood of a Tajima genealogy ${\textbf{g}}{}$ is to sum over all possible allocations of mutations to its branches. This can be efficiently done by exploiting the augmented perfect phylogeny representation of the data [**T**]{} and by first mapping nodes of [**T**]{} to subtrees of [**g**]{}. We stress that the need for an allocation step arises only when working with Tajima genealogies. In Kingman’s coalescent, tree leaves are labeled by the sequences to which they correspond, and so there is a unique possible allocation. In Tajima’s coalescent, leaves are unlabeled, creating potential symmetries in the tree, and so we have to scan all the possible ways in which the observed sequences may 