  We study a character-based phylogeny reconstruction problem when an
incomplete set of data is given. More specifically, we consider the situation
under the directed perfect phylogeny assumption with binary characters in which
for some species the states of some characters are missing. Our main object is
to give an efficient algorithm to enumerate (or list) all perfect phylogenies
that can be obtained when the missing entries are completed. While a simple
branch-and-bound algorithm (B&B) shows a theoretically good performance, we
propose another approach based on a zero-suppressed binary decision diagram
(ZDD). Experimental results on randomly generated data exhibit that the ZDD
approach outperforms B&B. We also prove that counting the number of
phylogenetic trees consistent with a given data is #P-complete, thus providing
an evidence that an efficient random sampling seems hard.
