Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures Conference Paper uri icon


MeSH Major

  • Acute Kidney Injury
  • Cardiac Surgical Procedures
  • Central Venous Pressure
  • Renal Insufficiency


  • 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. © 2014 Springer-Verlag Berlin Heidelberg.

publication date

  • January 2014



  • Conference Paper


Digital Object Identifier (DOI)

  • 10.1007/978-3-662-44753-6_27

Additional Document Info

start page

  • 354

end page

  • 367


  • 8701 LNBI