Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples
- Hujdurovic, Ademir University of Primorska, Slovenia
- Kacar, Ursula Celtra Inc., Slovenia
- Milanic, Martin University of Primorska, Slovenia
- Ries, Bernard University of Fribourg, Switzerland
- Tomescu, Alexandru I. University of Helsinki, Finland
-
2018
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 https://github.com/alexandrutomescuMixedPerfectPhylogeny.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 328809
- DOI 10.1109/TCBB.2016.2606620
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308594
Statistics
Document views: 36
File downloads:
- rero.pdf: 155