TY - GEN
T1 - Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures
AU - Hajirasouliha, Iman
AU - Raphael, Benjamin J.
N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - High-throughput sequencing of cancer genomes have motivated the problem of inferring the ancestral history of somatic mutations that accumulate in cells during cancer progression. While the somatic mutation process in cancer cells meets the requirements of the classic Perfect Phylogeny problem, nearly all cancer sequencing studies do not sequence single cancerous cells, but rather thousands-millions of cells in a tumor sample. In this paper, we formulate the Perfect Phylogeny Mixture problem of inferring a perfect phylogeny given somatic mutation data from multiple tumor samples, each of which is a superposition of cells, or "species." We prove that the Perfect Phylogeny Mixture problem is NP-hard, using a reduction from the graph coloring problem. Finally, we derive an algorithm to solve the problem.
AB - High-throughput sequencing of cancer genomes have motivated the problem of inferring the ancestral history of somatic mutations that accumulate in cells during cancer progression. While the somatic mutation process in cancer cells meets the requirements of the classic Perfect Phylogeny problem, nearly all cancer sequencing studies do not sequence single cancerous cells, but rather thousands-millions of cells in a tumor sample. In this paper, we formulate the Perfect Phylogeny Mixture problem of inferring a perfect phylogeny given somatic mutation data from multiple tumor samples, each of which is a superposition of cells, or "species." We prove that the Perfect Phylogeny Mixture problem is NP-hard, using a reduction from the graph coloring problem. Finally, we derive an algorithm to solve the problem.
KW - Cancer genomics
KW - DNA sequencing
KW - Graph coloring
KW - perfect phylogeny
UR - http://www.scopus.com/inward/record.url?scp=84975885945&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84975885945&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-44753-6_27
DO - 10.1007/978-3-662-44753-6_27
M3 - Conference contribution
AN - SCOPUS:84975885945
SN - 9783662447529
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 354
EP - 367
BT - Algorithms in Bioinformatics - 14th International Workshop, WABI 2014, Proceedings
PB - Springer Verlag
T2 - 14th International Workshop on Algorithms in Bioinformatics, WABI 2014
Y2 - 8 September 2014 through 10 September 2014
ER -