CRII: AF: Towards an Accurate and Complete Characterization of the Solution Space in Phylogeny Estimation from Mixed Samples

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Cancers result from an evolutionary process during which mutations accumulate in a population of cells, leading to the presence of distinct cellular populations within the same tumor with varying complements of mutations. Thus, to understand and treat cancer, researchers must view the disease through the lens of evolution. Phylogenetic trees, or phylogenies, are mathematical models to describe the evolutionary history and relationships of entities observed at the present time. They have been traditionally applied to study biological species and languages. In the context of cancer, tumor phylogenies are essential to improve our understanding of basic mechanisms of cancer progression, and to develop personalized cancer treatment plans tailored to the unique evolutionary history of a patient's tumor. This project addresses a challenge that is unique to cancer phylogenetics, i.e. phylogeny inference from mixed tumor samples, which form the majority of current cancer sequencing studies. While a biological sample in traditional phylogenetics contains sequences from cells with identical genomes, a mixed tumor sample is composed of sequences from cells with distinct genomes. Consequently, multiple phylogenetic trees may be inferred from the same mixed input samples, potentially leading to diverging conclusions in downstream clinical and basic science analyses of cancers. To address this challenge, this project seeks new algorithms, theory and practical implementations for characterizing the solution space in phylogeny estimation from mixed tumor samples. In addition, this award will support the advancement, training and education of students at all levels through course and outreach module design. The underlying combinatorial problem of current cancer phylogenetics methods is the Perfect Phylogeny Mixture (PPM) problem, where, given an m-by-n mutation frequency matrix F, the task is to infer a two-state perfect phylogeny tree T that explains the composition of the m mixed samples and the evolutionary history of the n mutations. This problem is not only nondeterministic polynomial time (NP) complete, but it also exhibits non-uniqueness of solutions, i.e. multiple perfect phylogeny trees T may explain a single input mutation frequency matrix F. Multiple solutions may lead to alternate conclusions in downstream analyses in cancer genomics. Thus, it is important to accurately and completely characterize the solution space by, for instance, generating solutions uniformly at random. However, current methods are unable to do so. This project will address these shortcomings through the following three research activities. First, this project will characterize conditions for statistical identifiability for the PPM model, which is a fundamental question in phylogenetics. Second, this project will develop almost uniform sampling and approximate counting algorithms that incorporate a probabilistic data error model. Third, the team of researchers will apply the resulting algorithms in a variety of downstream analyses in cancer to assess robustness of conclusions in the light of uncertainty due to non-uniqueness. Importantly, the new mathematical and computational techniques developed as part of this project will be applicable to other settings where multiple optima are encountered. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.