Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.
IEEE/ACM Trans Comput Biol Bioinform
; 15(1): 96-108, 2018.
Article
en En
| MEDLINE
| ID: mdl-28113405
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.
Texto completo:
1
Colección:
01-internacional
Base de datos:
MEDLINE
Asunto principal:
Filogenia
/
Algoritmos
/
Biología Computacional
/
Neoplasias
Tipo de estudio:
Diagnostic_studies
/
Prognostic_studies
Límite:
Humans
Idioma:
En
Revista:
ACM Trans Comput Biol Bioinform
Asunto de la revista:
BIOLOGIA
/
INFORMATICA MEDICA
Año:
2018
Tipo del documento:
Article
Pais de publicación:
Estados Unidos