2026-09-20T23:55:47Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/104916 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

El-Kebir, Mohammed Xie, Shunping 2019-08-23T20:01:16Z 2019-08-23T20:01:16Z 2019-04-25 2019-05 Cancer cells may mutate multiple times, from a normal state to a mutated state and vice versa. Given our sequenced data, we can model the mutation process with a phylogenetic tree. One representative model is the k-Dollo parsimony, where all observed mutations mutate from a single normal cell and each character of a cell is gained at most once and lost at most k times. We examine the 1-Dollo Phylogeny problem, does a 1-Dollo phylogeny, a tree that follows the 1-Dollo parsimony model, exist for the observations. Current algorithms to solve the 1-Dollo Phylogeny problem only tell us whether or not a set of observations has a 1-Dollo phylogeny by outputting a single solution. We explore the structure of 1-Dollo phylogenies and use our idea of a skeleton to develop an algorithm that enumerates all 1-Dollo phylogenies for any set of observations. This algorithm runs much faster than the naive brute force enumeration algorithm for random input. The implementation is here: https://github.com/sxie12/skeleton_solver. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-08-22 without embargo terms The student, Shunping Xie, accepted the attached license on 2019-04-24 at 15:15. The student, Shunping Xie, submitted this Thesis for approval on 2019-04-24 at 15:17. This Thesis was approved for publication on 2019-04-25 at 07:39. DSpace SAF Submission Ingestion Package generated from Vireo submission #13858 on 2019-08-22 at 14:46:21 Made available in DSpace on 2019-08-23T20:01:16Z (GMT). No. of bitstreams: 2 XIE-THESIS-2019.pdf: 256136 bytes, checksum: d73d3f572be5eb7ed12c98e587f914c3 (MD5) LICENSE.txt: 4209 bytes, checksum: 9b3adbf48f426e8d4bb726d4c71f9722 (MD5) Previous issue date: 2019-04-25 application/pdf http://hdl.handle.net/2142/104916 en Copyright 2019 Shunping Xie 1-Dollo phylogeny Skeleton Enumeration algorithm Towards characterizing the solution space of the 1-Dollo Phylogeny problem text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.