Let G ¼ (S, E, w) be a directed, weighted graph where S ¼ {s 1 ,y, s n } is the set of vertices corresponding to the n sampled isolates, with associated collection dates T ¼ {t 1 ,y, t n }. E is the set of directed edges of G modeling all possible ancestries in S, such that (s i , s j )A E if and only if t i ot j . The weight function w: E-R assigns a weight to each possible ancestry, which reflects how credible each ancestry relationship is. For instance, w could be defined as a genetic distance or similarity, or as the log-likelihood resulting from a probabilistic model of evolution. The weight of a subset A of E is computed as w A ¼ P e2A wðeÞ. The 'best' genealogy of the sampled isolates is the spanning directed tree (that is, 'branching' reaching all the nodes) J ¼ (S,B,w) with BDE optimizing (that is, minimizing or maximizing) w B . Whenever sampled isolates form more than one connected set, the algorithm is applied to each connected set separately (see example in Figure 3b ). This problem has been solved by Edmonds (1967) and Chu and Liu (1965) , who developed an algorithm to find J so that w B is maximum or minimum. The algorithm proceeds by identifying optimum ancestors for each node at the exception of the root (the oldest isolate), and then recursively removes possible cycles. However, in our case, cycles are impossible as ancestries cannot go back in time, which greatly simplifies computations.