Files in this item

FilesDescriptionFormat

application/pdf

application/pdfXIE-THESIS-2019.pdf (256kB)
(no description provided)PDF

Description

Title:Towards characterizing the solution space of the 1-Dollo Phylogeny problem
Author(s):Xie, Shunping
Advisor(s):El-Kebir, Mohammed
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):1-Dollo phylogeny
Skeleton
Enumeration algorithm
Abstract: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.
Issue Date:2019-04-25
Type:Text
URI:http://hdl.handle.net/2142/104916
Rights Information:Copyright 2019 Shunping Xie
Date Available in IDEALS:2019-08-23
Date Deposited:2019-05


This item appears in the following Collection(s)

Item Statistics