Incomplete Directed Perfect Phylogeny in Linear Time

Reconstructing the evolutionary history of a set of species is a central task in computational biology. In real data, it is often the case that some information is missing: the Incomplete Directed Perfect Phylogeny (IDPP) problem asks, given a collection of species described by a set of binary characters with some unknown states, to complete the missing states in such a way that the result can be explained with a directed perfect phylogeny. Pe’er et al. [SICOMP 2004] proposed a solution that takes \(\tilde{\mathcal {O}}(nm)\) time (the \(\tilde{\mathcal {O}}(\cdot )\) notation suppresses polylog factors) for n species and m characters. Their algorithm relies on pre-existing dynamic connectivity data structures: a computational study recently conducted by Fernandez-Baca and Liu showed that, in this context, complex data structures perform worse than simpler ones with worse asymptotic bounds.