times. To account for this difference, we define a new Markov chain.

The present paper contains three main contributions: first, we propose a new lower-resolution continuous-time Markov chain (CTMC) which we call the Tajima *heterochronous* $n$-coalescent, that allows to model partially-labeled genealogies of heterochronous samples. Second, we introduce a new algorithm to compute the likelihood. Likelihood calculation in [@pal19] called BESTT relies on a backtracking algorithm that is computationally unfeasible for sample sizes greater than $35$. Our new algorithm can accommodate up to $100$ sequences. Lastly, we introduce new MCMC proposals for efficient exploration of the space of Tajima genealogies and do Bayesian nonparametric inference on $(N_e(t))_{t\geq 0}$.

The main challenge in employing Tajima genealogies for coalescent-based inference is that the sequence data can be allocated, *i.e.* mapped, to a given genealogy, in many possible ways. The allocation is necessary to compute the likelihood. To find all possible maps, [@pal19] use a backtracking algorithm that proceeds in a bottom-up fashion: starting from the tips of the tree, the algorithm moves along the tree to the root checking for possible allocations of subsets of the data [**Y**]{} to clades of the tree [**g**]{}. Our proposal reverts this process and proceeds in 