Quantifying and summarizing tumor phylogeny solution spaces

Cancer phylogenies are crucial for understanding tumor development and have significant clinical applications. However, due to the heterogeneity of cancer cells and limitations of current sequencing technologies, it is impractical to conclusively determine a single tree. Despite this, downstream analysis typically requires a single or a small number of trees per patient. As a result, cancer phylogeny inference methods that aim to enumerate all plausible trees quickly become unscalable as the number of mutations grows. Similarly, methods that attempt to sample high-likelihood phylogenies, often based on Markov Chain Monte Carlo (MCMC) techniques, exhibit biases in their sampling results. Another approach involves summarizing multiple possible trees into one or a few trees. However, these methods rely heavily on the quality of the given trees, which, as mentioned earlier, is challenging to enumerate or sample accurately. This thesis addresses these challenges from three aspects. In the first part, we delve into the challenges of cancer phylogeny inference using bulk data, more specifically, we study the hardness of enumeration and sampling of cancer phylogenies. We illustrate how the number of possible phylogenies grows exponentially. Additionally, we show that current sampling methods exhibit bias in their sampling results. Furthermore, we provide theoretical proof of the complexity of uniform sampling. This work establishes theoretical foundations for phylogeny inference from bulk data. In the second and third part, we focus on the problem of summarizing a given set of possible phylogenies with one or a few trees. In the second part, we generalize the problem of inferring a single consensus tree to inferring multiple consensus trees. We delve into the complexity of this problem and propose two methods to address it. We show that the multiple consensus tree is more capable and provides a better summary than a single consensus tree. In the third part, we explore the single consensus tree problem but under a different distance measure which provides a better resolution. We establish the NP-hardness of this problem under the specified distance measure. In the fourth part, we address the challenge by directly summarizing the solution space from bulk data with backbone trees. We introduce a novel method for inferring backbone trees, aimed at efficiently summarizing the solution space. We demonstrate that these back- bone trees offer a comparable summarization result to existing methods. Furthermore, we extend the method to expand these backbone trees into full trees. Our findings reveal that the full trees generated from this expansion process exhibit higher quality compared to current tree inference methods.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Qi, Yuanyuan

Contributors dc:contributor

• El-Kebir, Mohammed
• Warnow, Tandy
• Milenkovic, Olgica
• Oesper, Layla

• Cancer
• Intra-tumor Heterogeneity
• Consensus
• Infinite-sites Assumption

Statement dc:rights

• Copyright 2024 Yuanyuan Qi

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/125664

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125664