Journal article

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples

Show more…
Published in:
  • IEEE/ACM Transactions on Computational Biology and Bioinformatics. - 2018, vol. 15, no. 1, p. 96-108
English 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- ardness 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
Faculté des sciences économiques et sociales
Département d'informatique
  • English
Computer science
License undefined
Persistent URL

Document views: 4 File downloads:
  • rero.pdf: 11