On the non-uniqueness of solutions to the perfect phylogeny mixture problem

Dikshant Pradhan, Mohammed El-Kebir

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


Tumors exhibit extensive intra-tumor heterogeneity, the presence of groups of cellular populations with distinct sets of somatic mutations. This heterogeneity is the result of an evolutionary process, described by a phylogenetic tree. The problem of reconstructing a phylogenetic tree T given bulk sequencing data from a tumor is more complicated than the classic phylogeny inference problem. Rather than observing the leaves of T directly, we are given mutation frequencies that are the result of mixtures of the leaves of T. The majority of current tumor phylogeny inference methods employ the perfect phylogeny evolutionary model. In this work, we show that the underlying Perfect Phylogeny Mixture combinatorial problem typically has multiple solutions. We provide a polynomial-time computable upper bound on the number of solutions. We use simulations to identify factors that contribute to and counteract non-uniqueness of solutions. In addition, we study the sampling performance of current methods, identifying significant biases.

Original languageEnglish (US)
Title of host publicationComparative Genomics - 16th International Conference, RECOMB-CG 2018, Proceedings
EditorsAïda Ouangraoua, Mathieu Blanchette
Number of pages17
ISBN (Print)9783030008338
StatePublished - 2018
Event16th International Conference on Comparative Genomics, RECOMB-CG 2018 - Magog-Orford, Canada
Duration: Oct 9 2018Oct 12 2018

Publication series

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


Other16th International Conference on Comparative Genomics, RECOMB-CG 2018

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the non-uniqueness of solutions to the perfect phylogeny mixture problem'. Together they form a unique fingerprint.

Cite this