  The reconstruction of phylogenetic trees from mixed populations has become
important in the study of cancer evolution, as sequencing is often performed on
bulk tumor tissue containing mixed populations of cells. Recent work has shown
how to reconstruct a perfect phylogeny tree from samples that contain mixtures
of two-state characters, where each character/locus is either mutated or not.
However, most cancers contain more complex mutations, such as copy-number
aberrations, that exhibit more than two states. We formulate the Multi-State
Perfect Phylogeny Mixture Deconvolution Problem of reconstructing a multi-state
perfect phylogeny tree given mixtures of the leaves of the tree. We
characterize the solutions of this problem as a restricted class of spanning
trees in a graph constructed from the input data, and prove that the problem is
NP-complete. We derive an algorithm to enumerate such trees in the important
special case of cladisitic characters, where the ordering of the states of each
character is given. We apply our algorithm to simulated data and to two cancer
datasets. On simulated data, we find that for a small number of samples, the
Multi-State Perfect Phylogeny Mixture Deconvolution Problem often has many
solutions, but that this ambiguity declines quickly as the number of samples
increases. On real data, we recover copy-neutral loss of heterozygosity,
single-copy amplification and single-copy deletion events, as well as their
interactions with single-nucleotide variants.
