Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures

Iman Hajirasouliha, Benjamin J. Raphael

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 14th International Workshop, WABI 2014, Proceedings
PublisherSpringer Verlag
Pages354-367
Number of pages14
ISBN (Print)9783662447529
DOIs
StatePublished - 2014
Externally publishedYes
Event14th International Workshop on Algorithms in Bioinformatics, WABI 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8701 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Workshop on Algorithms in Bioinformatics, WABI 2014
Country/TerritoryPoland
CityWroclaw
Period9/8/149/10/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Cancer genomics
  • DNA sequencing
  • Graph coloring
  • perfect phylogeny

Fingerprint

Dive into the research topics of 'Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures'. Together they form a unique fingerprint.

Cite this