2015/06/25 by Ademir Hujdurović, Hujdurović, Ademir, Urša Kačar +7 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cancer Genomics and Diagnostics #Algorithms and Data Compression #Gene expression and cancer classification
paper · pdf · doi:10.48550/arxiv.1506.07675
Recently, Hajirasouliha and Raphael (WABI 2014) proposed a model for\ndeconvoluting mixed tumor samples measured from a collection of high-throughput\nsequencing reads. This is related to understanding tumor evolution and critical\ncancer mutations. In short, their formulation asks to split each row of a\nbinary matrix so that the resulting matrix corresponds to a perfect phylogeny\nand has the minimum number of rows among all matrices with this property. In\nthis paper we disprove several claims about this problem, including an\nNP-hardness proof of it. However, we show that the problem is indeed NP-hard,\nby providing a different proof. We also prove NP-completeness of a variant of\nthis problem proposed in the same paper. On the positive side, we propose an\nefficient (though not necessarily optimal) heuristic algorithm based on\ncoloring co-comparability graphs, and a polynomial time algorithm for solving\nthe problem optimally on matrix instances in which no column is contained in\nboth columns of a pair of conflicting columns. Implementations of these\nalgorithms are freely available at\nhttps://github.com/alexandrutomescu/MixedPerfectPhylogeny\n