title: Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.
abstract: 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.
authors.forename: Ademir
authors.initials: A
authors.lastname: Hujdurovic
authors.forename: Ursa
authors.initials: U
authors.lastname: Kacar
authors.forename: Martin
authors.initials: M
authors.lastname: Milanic
authors.forename: Bernard
authors.initials: B
authors.lastname: Ries
authors.forename: Alexandru I
authors.initials: AI
authors.lastname: Tomescu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D008957:Models, Genetic; D009369:Neoplasms / Q000145:classification / Q000235:genetics*; D010802:Phylogeny