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

癌症是一个进化过程的结果，在这个过程中，突变在细胞群中积累，导致同一肿瘤内存在不同的细胞群，具有不同的突变补体。因此，为了理解和治疗癌症，研究人员必须从进化的角度来看待这种疾病。系统发生树是描述目前观察到的实体的进化史和关系的数学模型。传统上，它们被用于研究生物物种和语言。在癌症的背景下，肿瘤系统发育对于提高我们对癌症进展的基本机制的理解，以及根据患者肿瘤的独特进化历史制定个性化的癌症治疗计划至关重要。该项目解决了癌症系统发育的独特挑战，即混合肿瘤样本的系统发育推断，这构成了当前大多数癌症测序研究。传统系统遗传学中的生物样本包含来自相同基因组的细胞序列，而混合肿瘤样本由来自不同基因组的细胞序列组成。因此，可以从相同的混合输入样本中推断出多个系统发育树，这可能导致下游癌症临床和基础科学分析的不同结论。为了应对这一挑战，该项目寻求新的算法、理论和实际实现，以表征混合肿瘤样本的系统发育估计中的解空间。此外，该奖项将通过课程和扩展模块设计支持各级学生的进步、培训和教育。当前癌症系统发育方法的潜在组合问题是完美系统发育混合（PPM）问题，其中，给定m × n突变频率矩阵F，任务是推断一个两态完美系统发育树T，该树解释了m个混合样本的组成和n个突变的进化史。这个问题不仅是非确定性多项式时间（NP）完备的，而且还表现出解的非唯一性，即多个完美的系统发育树T可以解释单个输入突变频率矩阵f。在癌症基因组学的下游分析中，多个解可能导致不同的结论。因此，准确和完整地表征解空间是很重要的，例如，随机均匀地生成解。然而，目前的方法无法做到这一点。本项目将通过以下三个研究活动来解决这些不足。首先，该项目将描述PPM模型的统计可识别性条件，这是系统发育学中的一个基本问题。其次，该项目将开发几乎统一的采样和近似计数算法，其中包含概率数据误差模型。第三，研究小组将结果算法应用于癌症的各种下游分析，根据非唯一性导致的不确定性评估结论的稳健性。重要的是，作为该项目一部分开发的新的数学和计算技术将适用于遇到多个最优解的其他设置。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.