  Recently, Hajirasouliha and Raphael (WABI 2014) proposed a model for
deconvoluting mixed tumor samples measured from a collection of high-throughput
sequencing reads. This is related to understanding tumor evolution and critical
cancer mutations. In short, their formulation asks to split each row of a
binary matrix so that the resulting matrix corresponds to a perfect phylogeny
and has the minimum number of rows among all matrices with this property. In
this paper we disprove several claims about this problem, including an
NP-hardness proof of it. However, we show that the problem is indeed NP-hard,
by providing a different proof. We also prove NP-completeness of a variant of
this problem proposed in the same paper. On the positive side, we propose an
efficient (though not necessarily optimal) heuristic algorithm based on
coloring co-comparability graphs, and a polynomial time algorithm for solving
the problem optimally on matrix instances in which no column is contained in
both columns of a pair of conflicting columns. Implementations of these
algorithms are freely available at
https://github.com/alexandrutomescu/MixedPerfectPhylogeny
