{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/125664"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/125664","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Quantifying and summarizing tumor phylogeny solution spaces","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","abstract_has_math":false,"creators":["Qi, Yuanyuan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["El-Kebir, Mohammed","Warnow, Tandy","Milenkovic, Olgica","Oesper, Layla"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-06-11","date_published":"2024-06-11","updated_at":"2026-07-22T22:25:02Z","subjects":["Cancer","Intra-tumor Heterogeneity","Consensus","Infinite-sites Assumption"],"languages":["en","eng"],"rights":["Copyright 2024 Yuanyuan Qi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/125664","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["El-Kebir, Mohammed","Warnow, Tandy","Milenkovic, Olgica","Oesper, Layla"]},{"key":"dc:creator","label":"Author","values":["Qi, Yuanyuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-06-11","2024-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Cancer","Intra-tumor Heterogeneity","Consensus","Infinite-sites Assumption"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Yuanyuan Qi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/125664"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","The student, Yuanyuan Qi, accepted the attached license on 2024-06-04 at 16:56.","The student, Yuanyuan Qi, submitted this Dissertation for approval on 2024-06-04 at 17:12.","This Dissertation was approved for publication on 2024-06-11 at 16:25.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20817 on 2025-02-04 at 21:15:40","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Quantifying and summarizing tumor phylogeny solution spaces"]}]}],"canonical_facts":{"dc:contributor":["El-Kebir, Mohammed","Warnow, Tandy","Milenkovic, Olgica","Oesper, Layla"],"dc:creator":["Qi, Yuanyuan"],"dc:date":["2024-06-11","2024-08"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","The student, Yuanyuan Qi, accepted the attached license on 2024-06-04 at 16:56.","The student, Yuanyuan Qi, submitted this Dissertation for approval on 2024-06-04 at 17:12.","This Dissertation was approved for publication on 2024-06-11 at 16:25.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20817 on 2025-02-04 at 21:15:40","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/125664"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Yuanyuan Qi"],"dc:subject":["Cancer","Intra-tumor Heterogeneity","Consensus","Infinite-sites Assumption"],"dc:title":["Quantifying and summarizing tumor phylogeny solution spaces"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}