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

CRII：AF：在混合样本的系统发育估计中实现解决方案空间的准确和完整的表征

• 批准号: 1850502
• 负责人: Mohammed El-Kebir
• 金额: $ 17.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-15 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1850502&HistoricalAwards=false
• 关键词: CRII; AF; Towards; Accurate; Complete

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.

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

项目成果

Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors

• DOI: 10.1186/s13015-019-0155-6
• 发表时间: 2019-09-03
• 期刊: ALGORITHMS FOR MOLECULAR BIOLOGY
• 影响因子: 1
• 作者: Qi, Yuanyuan;Pradhan, Dikshant;El-Kebir, Mohammed
• 通讯作者: El-Kebir, Mohammed

Parsimonious Clone Tree Reconciliation in Cancer

• DOI: 10.4230/lipics.wabi.2021.9
• 发表时间: 2021
• 作者: P. Sashittal;Simone Zaccaria;M. El-Kebir

Sampling and summarizing transmission trees with multi-strain infections

多菌株感染传播树的采样和总结

• DOI: 10.1093/bioinformatics/btaa438
• 发表时间: 2020
• 期刊: Bioinformatics
• 影响因子: 5.8
• 作者: Sashittal, Palash;El-Kebir, Mohammed
• 通讯作者: El-Kebir, Mohammed

Summarizing the solution space in tumor phylogeny inference by multiple consensus trees

• DOI: 10.1093/bioinformatics/btz312
• 发表时间: 2019-07-15
• 期刊: BIOINFORMATICS
• 影响因子: 5.8
• 作者: Aguse, Nuraini;Qi, Yuanyuan;El-Kebir, Mohammed
• 通讯作者: El-Kebir, Mohammed

Emerging Topics in Cancer Evolution

癌症进化的新兴话题

• DOI: 10.1142/9789811250477_0036
• 发表时间: 2021
• 期刊: Proceedings of the Pacific Symposium on Biocomputing 2022
• 作者: El-Kebir, Mohammed;Morris, Quaid;Oesper, Layla;Sahinalp, S. Cenk
• 通讯作者: Sahinalp, S. Cenk